8
$\begingroup$

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$?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Gjergji Zaimi
    Commented Sep 11, 2010 at 14:58
  • $\begingroup$ 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? $\endgroup$
    – Charles Siegel
    Commented Sep 11, 2010 at 15:06
  • 1
    $\begingroup$ 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? $\endgroup$
    – Gjergji Zaimi
    Commented Sep 11, 2010 at 15:18
  • $\begingroup$ 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. $\endgroup$
    – Charles Siegel
    Commented Sep 11, 2010 at 17:32

2 Answers 2

Reset to default
5
$\begingroup$

Actually a graph is called half-transitive if it is vertex and edge transitive, but not arc-transitive. I am going to assume here that the term means what you chose it to mean.

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.

For a second class of examples, there is a family of arc-transitive self-complementary graphs due to Peisert, which are strongly regular with the same parameters as the Paley graphs.

I do not know of examples of cospectral graphs which are half-transitive in the usual sense of the term. I am confident that there will be such things, but none may be known.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ah, until Gjergji pointed it out, I didn't know I was misusing the term half-transitive (I don't know the standard terminology here). Are Paley graphs vertex and edge transitive? And if not, is spectrum a complete invariant among vertex and edge transitive graphs? I'm rewriting the question, to make it more precise and correct language $\endgroup$
    – Charles Siegel
    Commented Sep 11, 2010 at 17:35
  • $\begingroup$ The Paley graphs are vertex and edge transitive, so graphs that are vertex and edge transitive are not characterized by their spectrum. $\endgroup$
    – Chris Godsil
    Commented Sep 13, 2010 at 4:06
4
$\begingroup$

As Chris said, the answer is most probably no, and most likely there are known such examples. There are many examples and constructions of non isomorphic graphs with the same spectrum and some of these examples are Cayley graphs and other very symmetric graphs. Cayley graphs are always vertex transitive and quite often, for a suitable choise of generators, also edge transitive. Some of these examples are based on a famous paper of Sunada. Sunada's method was originally for creating isospectral manifolds but it can be applied (and is even easier) to create isospectral graphs. The following paper by Bob Brooks "Isospecrtal graphs and isospectral surfaces" is a good starting point.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.