Is there any non-isomorphic cospectral regular graphs? Please suggest some examples or reference. Cospectral graphs are those graph which possess same set of spectrum.

  • $\begingroup$ I expect the answer in negative. but do not have justification for it. $\endgroup$ – G_0_pi_i_e Mar 1 '16 at 6:15

Yes, there are. Take an $n\times n$ Latin square $L$ and construct from it a graph as follows. The vertices of the graph are the $n^2$ positions in the Latin square. Two positions are adjacent in our graph if they are in the same row, the same column, or have the same entry. This gives a regular graph with valency $3n-3$. The eigenvalues of the graph are $3n-3$, $n-3$ and $-3$ with respective multiplicities $1$, $3n-3$ and $n^2-3n+2$. To get your first examples, take the two Latin squares arising as the multiplication tables of the groups of order four.

More generally, strongly regular graphs with the same parameters are cospectral. The `Latin square' graphs just given are examples of strongly regular graphs.

One place where this stuff is treated is Chapter 10 of "Algebraic Graph Theory" by Royle and me.

  • $\begingroup$ How can you justify that the graphs arising from two Latin squares are always nonisomorphic? $\endgroup$ – G_0_pi_i_e Mar 4 '16 at 3:19
  • $\begingroup$ Note that I did not claim that the graphs I constructed were always non-isomorphic. It can be shown that the graphs are isomorphic if and only if the Latin squares lie in what wikipedia calls the same main class. This best seen in terms of the associated orthogonal array; it is not hard to show that the graph determines the array and vice versa. $\endgroup$ – Chris Godsil Mar 4 '16 at 3:49
  • $\begingroup$ -Thank you. I got it. $\endgroup$ – G_0_pi_i_e Mar 4 '16 at 4:36

Cospectral Regular Graphs

Found it from 'Which graphs are determined by their spectrum?'; Edwin R. van Dam, Willem H. Haemers; Linear Algebra and its Applications 373 (2003) 241–272


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.