Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Here's a counterexample with $8$ vertices. –  joriki Feb 7 '12 at 22:28
    
@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? –  Hooked Feb 7 '12 at 22:58

1 Answer 1

up vote 5 down vote accepted

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$.

share|improve this answer
1  
I checked this result (here's the code). This is the only example on $6$ vertices, and indeed the smallest. The characteristic polynomial is $$x^6-7x^4-4x^3+7x^2+4x-1=(x+1)^2(x-1)(x^3-x^2-5x+1)\;.$$ On $7$ vertices there are 31 characteristic polynomials associated with more than one connected graph; only one is connected with three graphs, $$-x^7+11x^5+10x^4-16x^3-16x^2=-x^2(x+1)(x+2)(x^3-3x^2-4x+8)\;;$$ the edges are A-B A-C A-D A-E C-E D-E A-F C-F D-F A-G B-G; A-C B-C B-D A-E B-E C-E D-E B-F C-F D-F A-G; A-B A-C B-C A-E B-E C-E D-E C-F D-F A-G B-G. –  joriki Feb 8 '12 at 7:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.