# inverse eigenvalue problem on graph laplacian

I am trying to construct a graph Laplacian matrix from a set of eigenvalue. I've read several papers about inverse eigenvalue problems but to be honest I didn't understand clearly. Could somebody provide me a general idea about inverse eigenvalue algorithms? Which algorithm is the best for me to choose? Or a concrete example. Below is a detailed description of my question:

Suppose we have a connected undirected graph $G$ with $n$ vertices. $L$ is the Laplacian matrix of $G$, then the eigenvalues of $L$ have the form $$0 = \lambda_0 \le \lambda_1 ... \le \lambda_n$$ Now if I slightly change $\lambda_1$ with arbitrary amount to $\lambda_1$* (still in the same form) is it possible to construct another graph Laplacian matrix by this new set of eigenvalues $\{$ $\lambda_0$, $\lambda_1$* $...$ $\lambda_n$ $\}$?

I know that only finite number of sets can be the eigenvalues of a graph laplacian matrix. Does the eigenvalues have any particular form to be the eigenvalues of a Laplacian matrix?

Thanks very much!

-
Maybe you could give an example of what you want to do. A list of n numbers might not be the eigenvalues of a graph, in fact only finitely many are. And the eigenvalues of a graph can also be the eigenvalues of another graph. – Aaron Meyerowitz Dec 1 '10 at 4:22
There are also inverse eigenvalue problems that concern not the uniquely defined Laplacian where every nonzero off-diagonal entry is exactly $-1$, but rather consider the entire set of generalized Laplacians, where the entries that are $-1$ in the Laplacian can be any strictly negative numbers, and the diagonal entries are chosen so that each row sums to $0$. It is in the setting of generalized Laplacians that it often makes the most sense to talk about small perturbations of the spectrum. Could the papers you are reading be about generalized Laplacians? – Tracy Hall Dec 1 '10 at 10:04
For the standard graph Laplacian, the answer to your question is no: Since the diagonal entries are integers the trace is too, which is also the sum of the eigenvalues. Changing one eigenvalue by less than $1$ while keeping the others fixed will spoil that property. – Tracy Hall Dec 2 '10 at 6:42