Not isomorphic graphs with same spectrum - exists?

1.2k Views Asked by At

I am wondering if there exists two graphs, which are not isomorphic with the condition that both of them have the same spectrum.

Two graphs are isomorphic when they may be drawn in the same way.

Spectrum I mean set of all eigenvalues of the matrix of the graph.

https://en.wikipedia.org/wiki/Spectrum_of_a_matrix

Anybody may give me hint or some suggestions ? Or maybe this problem is already solved in math ?

I have seen the closiest topic to mine: Given two non-isomorphic graphs with the same number of edges, vertices and degree, what is the most efficient way of proving they are not isomorphic?, however it is not direct answer to mine wonders, since the eigenvalues may be different in those graphs if I am correct.

1

There are 1 best solutions below

1
On

Graph spectrum is the set of its eigenvalues, here. Two graphs are isomorphic if they have the same number of vertices connected in the same way, here.

Here is an example of two graphs that have the same spectrum, but are not isomorphic. Both have the same set of eigenvalues $\{0, \sqrt{6}, -\sqrt{6}\}$

enter image description here

Here is the resource, a lecture by Bojan Mohar. The whole playlist is worth watching. Using graph Laplacian spectrum instead of just the adjacency spectrum gives better insight into the graph properties.