In Linial's presentation on SOME PROBLEMS AND RESULTS IN THE GEOMETRY OF GRAPHS, on slide 7, some relations of properties of graphs to the eigenvalues of their adjacency matrix are listed, e.g.
- if $G$ is $d$-regular, then $\lambda_1=d$ and the eigenvector $v_1=1/\sqrt{n}$
- $G$ is connected iff $\lambda_1\gt\lambda_2$
- $G$ is bipartite iff $\lambda_1=-\lambda_n$
- $\chi(G)\ge-\frac{\lambda_1}{\lambda_n}+1$
That leads to the idea of generating random graphs with certain properties by incorporating constraints on eigenvalues and eigenvectors into their generation rather than gambling with probabilistic guarantees.
Question:
what is known about the problem of generating random graphs with a given number of vertices, whose (binary) adjacency matrix has a set of given eigenvalues and possibly also corresponding eigenvectors when the graphs are symmetric and have no parallel edges or self loops?
