Essentially as the title, but I'll give a little bit more background.


I have some finite graph $G$ with $n$ vertices and adjacency matrix $A$. Let $D$ be the $n$ by $n$ matrix with the degree of vertex $i$ at the $i,i$ entry, and 0's everywhere. Finally, let $L = D - A$ be the (unnormalized) graph Laplacian of $G$. Next, fix some collection of eigenvectors and eigenvalues of $L$.


My big-picture question is: Under what conditions are there other graphs which share those eigenvectors/values? 


With a little more precision: Approximately how many eigenvectors & eigenvalues can be specified before the answer is no? About how many graphs are there when the answer is yes?


It seems likely that the answer would be a little complicated. I know a few special cases (e.g. 2 eigenvectors/values determine cycles completely; on the other hand, as long as the average degree is fairly large, there are generally very many graphs with the same bottom eigenvector). I certainly appreciate hearing about conditions which aren't tight, as long as they are at least a little broad.


I'm interested in the situation where the eigenvectors DON'T determine the graph, so I would also appreciate any literature pointers to `relaxations' of this idea. For example, one could imagine requiring that the Laplacian contracts the eigenvectors by at least a certain amount (this certainly allows many graphs, but that space is pretty big). In another direction, it seems plausible there is some analogue in the language of graphons. 


Thanks for any help!



When Do a Few Eigenvectors of Graph Laplacians Not Determine the Graph?
The experimental evidence for adjacency matrices suggests that, for a random graph, its characteristic polynomial is irreducible over the rationals. I would expect that the characteristic polynomial of the Laplacian of a random graph on $n$ vertices would have one irreducible factor of degree $n-1$. However, while it easy is to convince yourself of this by testing on random graphs, absolutely nothing has been proved.


If we move away from the generic case, things become much more complicated. 
All circulant graphs can be assumed to have the same orthogonal basis of eigenvectors
(a Vandermonde matrix) and there are examples of cospectral circulants. (Note
that for regular graphs, the adjacency matrix and the Laplacian have the same eigenvectors, and provide the same spectral information.) So now we
have nonisomorphic graphs with the same eigenvalues and eigenvectors. Hence we must assume that we are given pairs (eigenvalue, eigenvector). This is not quite enough, because our eigenvalues need not be simple. It would seem that our data
will be pairs consisting of an eigenvalue and the matrix representing orthogonal
projection onto the corresponding eigenspace.


Let $M$ be a $d\times m$ binary matrix with linearly independent rows.
Let $X(M)$ be the graph with the elements of $\mathbb{Z}\_2^d$ as its vertices,
two adjacent if and only if their difference is a column of $M$. Such a graph
is a Cayley graph for $\mathbb{Z}\_2^d$, and is known as a cubelike graph.
The characters of $\mathbb{Z}\_2^d$ are eigenvectors, and the eigenvalues
are integers. The eigenvalues and their multiplicities are determined by the weight enumerator of the binary code generated by the rows of $M$ - a code word of weight $k$ gives an eigenvalue $m-2k$. Since there are nonisomorphic binary codes with the same weight enumerator, there are cospectral cubelike graphs. I do not know
how much eigendata two cubelike graphs may have in common, but this would
seem a good place to look.


EDIT: Let $G$ be a graph with vertex set $\{1,\ldots,n\}$. Let $H$ be a graph with
vertex set $\{\pm1,\ldots,\pm n\}$; if $i$ and $j$ are adjacent in $G$, let
$(i,j)$ and $(-i,-j)$ be edges in $H$, and if $i$ and $j$ are not adjacent 
in $G$, let $(i,-j)$ and $(-i,j)$ be edges. (Note that $H$ is regular 
with valency $n-1$.) Call $H$ the two-graph constructed from $G$.


Let $\pi$ be the partition of $V(H)$ with cells $\{i,-i\}$.
Then the subspace of $\mathbb{R}^{2n}$ formed by the vectors constant on cells
of $\pi$ is invariant under the adjacency matrix of $H$. It is the direct
sum of the span of the constant vectors (which has dimension 1) and the
vectors constant on cells that sum to 0 over $V(H)$. The second subspace is 
an eigenspace for $A(H)$, with eigenvalue $-1$. Since the space of vectors
constant on cells does not depend on the structure, distinct two-graph
on $2n$ vertices have $n$ eigenvectors and eigenvalues in common. (The spectrum of
a two-graph is the union of the spectrum of $K\_n$ and the spectrum of $2A(G)+I-J$).


