1
$\begingroup$

In the end of chapter $5$ of the book Spectra of Graphs of Cvetkovic, Doob, and Sachs, it is stated that for any pair of finite groups $\gamma_1$ and $\gamma_2$, there is a pair of cospectral graphs $G_1$ and $G_2$, whose automorphism groups are the groups mentioned.

From this statement, one can understand that there is little or no relation between the spectrum and automorphism group of graphs.

Question: If we restrict ourselves to cospectral $k$-regular graphs, can we compare their automorphism groups in any way?

$\endgroup$
2
$\begingroup$

Eric Mendelsohn proved that every finite group is the automorphism group of a Steiner triple system. The block graph of a Steiner triple system is strongly regular and its parameters are determined by the number of points of the system, hence the block graphs of Steiner triple systems on $v$ points are all cospectral. It is also known that almost all Steiner triple systems are asymmetric.

So assuming more regularity does not help in getting a useful correlation between spectrum and automorphism group.

$\endgroup$
  • $\begingroup$ Thank you! That was very helpful! I was hoping there was a relation between the spectrum of the edge adjacency matrix and the automorphism group. But this shows otherwise. $\endgroup$ – João Matias Mar 9 '18 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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