6
$\begingroup$

Graphs are cospectral if they have the same set of eigenvalues together with their algebraic multiplicities. How can one show that graphs such as these have the same odd girth?

$\endgroup$
  • $\begingroup$ I'm not sure this is necessarily true, as stated. Cospectral Graphs. The smallest example they name is $C_4 \cup K_1$ and $K_{1,4}$ which both have graph spectrum $(-2)0^{3}2$. However, $C_4 \cup K_1$ has girth 4, while $K_{1,4}$ is acyclic. (I'm not sure what it's girth should be then...probably $\infty$). It's possible this is just an exception, and you need more assumptions in your statement. Perhaps you require they're connected graphs. $\endgroup$ – Paddling Ghost Aug 29 '15 at 17:12
  • $\begingroup$ I would look here. I suspect this property of eigenvalues and powers of matrices has something to do with this. $\endgroup$ – Paddling Ghost Aug 29 '15 at 17:19
  • $\begingroup$ @Paddling Ghost: last time I checked, 4 was not odd :) $\endgroup$ – Leen Droogendijk Aug 29 '15 at 17:26
  • $\begingroup$ but the OP asks to prove if two graphs are cospectral, then they have the same odd girth." I presented a pair of cospectral graphs that do not have the same odd girth, in fact their girth's aren't odd at all. Note, the statement is not If two graphs with odd girth are cospectral, then they have the same girth. Right? $\endgroup$ – Paddling Ghost Aug 29 '15 at 17:33
  • 2
    $\begingroup$ The odd girth of $C_4\cup K_1$ is $\infty$, just like the odd girth of $K_{1,4}$ $\endgroup$ – Leen Droogendijk Aug 29 '15 at 17:35
4
$\begingroup$

Let $A$ be the adjacency matrix of one graph $G$, and $B$ the adjacency matrix of another graph $H$ which is cospectral to $G$. Thus $\text{tr}(A^k)=\text{tr}(B^k)$ for all nonnegative integers $k$.

Recall that the $(i,i)$-entry of $A^k$ is the number of walks of length $k$ starting and ending at vertex $i$. Similarly for $B$ of course.

Without loss of generality, suppose that the odd girth $g$ of $G$ is smaller than the odd girth of $H$. So we know there exists at least one closed walk of length $g$ in $G$ and so $\text{tr}(A^g)> 0$.

On the other hand, there cannot be any closed walks of length $g$ in $H$ since the odd girth of $H$ is larger than $g$ and so any closed walk of length $g$ could only consist of even cycles or repeated edges, in which case the walk would be of even length$^*$, contradicting the oddness of $g$. Hence $\text{tr}(B^g)=0$, contradicting the fact in the first paragraph above.

$*$ This part should be argued more rigorously than I have done, but that's the idea.

$\endgroup$
  • $\begingroup$ Thanks @Casteels for the answer here, I am so convinced that it is correct. $\endgroup$ – Patrick Chidzalo Sep 1 '15 at 5:49
  • $\begingroup$ I have realized that this answer is correct and already vigorous @Casteels $\endgroup$ – Patrick Chidzalo Sep 3 '15 at 17:33

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.