# Reverse Graph Spectra Problem?

Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph).

But what about the reverse problem? Given $n$ eigenvalues, can one (efficiently) find a graph that has this spectra?

I suspect that in general this is hard to do (and might be equivalent to GI) but what if you relax some of the conditions a bit? What if you make conditions that there is no multiplicity of eigenvalues? What about allowing graphs that have "close" spectra by some distance metric?

Any references or ideas would be welcome.

EDIT:

As Suresh points out, if you allow undirected weighted graphs with self loops, this problem becomes pretty trivial. I was hoping to get answers on the set of undirected, unweighted simple graphs but I would be happy with simple unweighted directed graphs as well.

• I think you might need to modify the question to 'unweighted undirected graphs with no self loops' or something like that ? I can imagine constructing a diagonal matrix with the required eigenvalues and declaring it to be a disconnected graph with weighted selfloops ? – Suresh Venkat Dec 11 '10 at 19:47
• Even simpler question (I don't know the answer) is how to construct simple connected graphs whose top few eigenvalues are given – Yaroslav Bulatov Dec 12 '10 at 1:07
• An alternative way of stating the question (the version with simple undirected graphs) is: given n real numbers (in some format), decide whether there exists an n×n symmetric 0/1 matrix with zero diagonals such that its n eigenvalues are the given numbers. – Tsuyoshi Ito Dec 12 '10 at 1:12
• @Yaroslav: I am not sure, but that problem sounds harder to me than the case where all n eigenvalues are given. – Tsuyoshi Ito Dec 12 '10 at 12:57
• Tiny observation: If we have no restrictions on the eigenvalues, the problem is really hard (even not include the algorithmic part) since this will implies the (non-)existence to the 57-regular Moore graph, which the eigenvalues are all known. – Hsien-Chih Chang 張顯之 Dec 12 '10 at 17:41