Question: Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the [Laplacian](http://en.wikipedia.org/wiki/Laplacian_matrix)) eigenvalue decomposition (also called the [spectra of a graph](http://en.wikipedia.org/wiki/Spectral_graph_theory)).

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.

Answer: 
Even asking whether a graph with a given spectrum exists is a tough question. This is witnessed by the [open problem](https://en.wikipedia.org/wiki/Moore_graph) of determining whether there exists a graph of girth 5 diameter 2 and order 3250 whose spectrum (if it exists) is known.
One other obstacle in defining your question is that the are isospectral (same eigenvalues) but non-isomorphic graphs. So given a list of eigenvalues in such a case, which graph do you want? Maybe you just want an algorithm to return one random element of the set of such non-isomorphic graphs?