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.
Reverse Graph Spectra Problem?
ds.algorithms;graph theory;graph algorithms;spectral graph theory