# Are vertex and edge-transitive graphs determined by their spectrum?

A graph is called vertex and edge transitive if the automorphism group is transitive on both vertices and edges.

The spectrum of a graph is the collection (with multiplicities) of eigenvalues of the incidence matrix.

Supposedly, it is conjectured that almost all graphs have the property that they are the unique graph with their spectrum (at least, according to MathWorld).

If $\Gamma_1,\Gamma_2$ are two vertex and edge transitive graphs, with the same valence, which are isospectral (have the same spectrum) then does it follow that $\Gamma_1\cong \Gamma_2$?

• Half transitive graphs also have the property that they are not arc transitive (=symmetric). If you are only interested in vertex+edge transitive graphs then there are small counterexamples of such cospectral graphs. There are conjectures that all regular and cospectral graphs have a very particular form, but I think your question is still open. Sep 11 '10 at 14:58
• Ah, I'm not a graph theorist in any way, shape or form, and was unaware. I don't want to rule out arc-transitive graphs, then. If they are cospectral, regular of the same degree, and both are vertex and edge symmetric, is anything known? Sep 11 '10 at 15:06
• The rook graph on a 4x4 board and mathworld.wolfram.com/ShrikhandeGraph.html form a cospectral pair, but they are both arc-transitive. There is some work on cospectral regular graphs, but I don't think there are any deep results on symmetric ones. By the way, does your question come from some finitary statement about cospectral manifolds? Sep 11 '10 at 15:18
• It doesn't, actually. It comes from algebraic geometry and studying certain incidence relations, and trying to show that there is a unique incidence satisfying some properties, to construct an action of its automorphism group on a certain moduli space. Sep 11 '10 at 17:32

Van Dam and Koolen construct distance-regular graphs with the same parameters (and hence the same spectrum) as the Grassmann graphs. They show that their graphs are not vertex transitive. The Grassmann graphs are distance transitive, and hence both arc and edge transitive. (Remark: the vertices of the Grassmann graph $G_q(v,k)$ are the $k$-dimensional subspaces of a vector space of dimension $v$ over the field of order $q$, two subspaces are adjacent if their intersection has dimension $k-1$.) If you google on Van Dam and Koolen, you'll easily find their paper.