Example of two non isomorphic graphs with 3 nodes and the same spectrum

eigenvalues-eigenvectorsgraph theory

It Is well known that there exists graphs, which are not isomorphic, that share the same spectrum (i.e. the set of all eigenvalues of the adiacency matrix of the graph).

We can find some examples of the here, for instance:

Not isomorphic graphs with same spectrum – exists?

Anyway, the resulting adiacency matrix is a $7\times 7$ Matrix. Does anyone know any simpler examples? In particular I am wondering if there exists two non isomorphic graphs with 3 nodes and the same spectrum.

Best Answer

By wiki, the smallest pair of cospectral mates is $\{K_{1,4}, C_4 ∪ K_1\}$, comprising the $5$-vertex star and the graph union of the 4-vertex cycle and the single-vertex graph, as reported by Collatz and Sinogowitz in 1957. Thus, there does not exist two non isomorphic graphs with at most 4 verties having the same spectrum.

If you are interested in finding more cospectral graphs, you can use the sage program below.

sage: g=graphs.cospectral_graphs(6)
sage: sorted(sorted(g.graph6_string() for g in glist) for glist in g)

Outputs (5 pairs of 6-vertex cospectral graphs) :

[['E`a?', 'Eh_?'],
 ['Ep__', 'Er?G'],
 ['Er??', 'Es_?'],
 ['Eto?', 'Ez?G'],
 ['ExGg', 'ExoG']]

enter image description here Be careful: I didn't really look at what's going on inside the function cospectral_graphs. My worry is that there may exist two non-isomorphic graphs that are not cospectral but have infinitely close (numerically) spectra, which are also classified as cospectral graphs by the program.

Related Question