3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What if I consider the spectrum along with the multiplicities? $\endgroup$ – kishlaya Jan 27 at 6:35

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.