nonisomorphic cospectral regular graphs

Question

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.

Answer 1

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.

Answer 2

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