MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 added 1065 characters in body

EDIT: Let $G$ be a graph with vertex set ${1,\ldots,n}$. Let $H$ be a graph withvertex 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 cellsof $\pi$ is invariant under the adjacency matrix of $H$. It is the directsum of the span of the constant vectors (which has dimension 1) and thevectors 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 vectorsconstant on cells does not depend on the structure, distinct two-graphon $2n$ vertices have $n$ eigenvectors and eigenvalues in common. (The spectrum ofa two-graph is the union of the spectrum of $K_n$ and the spectrum of $2A(G)+I-J$).
show/hide this revision's text 1

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.