5
$\begingroup$

Two graphs $G_1$ and $G_2$ that are cospectral (eigenvalue multisets from their adjacency matrices are the same), do not have to be isomorphic. The pair of cospectral graphs that serve as the smallest counterexample to isomorphism are the disjoint graph union of $C_4 \cup K_1$ and the star graph $S_5$.

What is the smallest counterexample known when we require that $G_1$ and $G_2$ are connected?

  • 0
    @joriki I saw that one after I posted the question, is it known to be the smallest for all connected graphs or just polyhedral ones?2012-02-07

1 Answers 1

5

Harary, King, Mowshowitz, Read, Cospectral graphs and digraphs, Bull London Math Soc 3 (1971) 321-328, give an example of two connected, cospectral, nonisomorphic graphs on 6 vertices, and claim, on the basis of exhaustive search, that it's the smallest.

EDIT: Here's the example. Let the vertices be $A,B,C,D,E,F$. For one graph, join $A$ to each of the other vertices, then join $BC$ and $DE$. For the other, draw a path $ABCDE$, then join $F$ to $B,C,D$.

  • 0
    No I have not, but I will go look it up. I am an amateur at best :). I am about to dive into the recorded lectures discussed in this article https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem2015-11-20