4 problems

For each integer $n\geq 2$, let $m(n)$ denote the least number of edges such that every graph on $n$ vertices with at least $m(n)$ edges has a matrix realization with two distinct…

Let $K_n$ be the complete graph on $n$ vertices, and let $H$ be a subgraph of $K_n$ with $|E(H)|\leq n-3$. Write $K_n\backslash H$ for the graph obtained by removing the edges of…

Let $G$ be a connected graph, let $A$ be its adjacency matrix, let $d_v$ denote the degree of vertex $v$, and let $D$ be the diagonal degree matrix. Thus $D^{1/2}\mathbf{1}$ is the…

Let $G$ be a connected graph, let $A$ be its adjacency matrix, and let $\mathcal{L}$ be its normalized Laplacian. A graph is regular if all its vertices have the same degree, and b…