7
$\begingroup$

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:

If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ strictly exceeds the largest root of the matching polynomial $\mu_G(z)$.

There appears to be very little published on the roots of the matching polynomial.

How might this conjecture be proved?

$\endgroup$
1

1 Answer 1

9
$\begingroup$

The moments (power symmetric functions, sums of powers of the roots of) the characteristic polynomial enumerate all closed walks in the graph. Chris Godsil proved that the moments of the matching polynomial count a particular type of closed walk, called tree-like. Graphs with cycles have some closed walks that are not tree-like. This proves that the even moments of the characteristic polynomial are eventually strictly greater than those of the matching polynomial if there is a cycle. That is, if the roots of the characteristic polynomial are $\lbrace \lambda_i\rbrace$ and those of the matching polynomial are $\lbrace \mu_i\rbrace$ then for large enough $k$, $$\sum \lambda_i^{2k} \gt \sum\mu_i^{2k},$$ which proves that $\lambda_{\rm max}\ge \mu_{\rm max}$.

Now restrict it to the connected case. The matching polynomial has a simple largest root $\mu_{\rm max}$ and also $-\mu_{\rm max}$ as a simple root. The characteristic polynomial has a simple largest root $\lambda_{\rm max}$ and may or may not have $-\lambda_{\rm max}$ as a simple root too (iff the graph is bipartite). Let $w_{2k}$ and $t_{2k}$ be the counts of all closed walks and all tree-like closed walks, respectively. Then as $k\to\infty$ either $w_{2k}\sim \lambda_{\rm max}^{2k}$ or $w_{2k}\sim 2\lambda_{\rm max}^{2k}$, while $t_{2k}\sim 2\mu_{\rm max}^{2k}$.

Now suppose there is a cycle of length $g$. An example of a closed walk that isn't tree-like is to start with a tour around the cycle twice then take any closed walk. So for $k$ large enough $w_{2k} \ge t_{2k}+t_{2k-2g}$. Therefore $w_{2k}$ is asymptotically at least $c\mu_{\rm max}^{2k}$ where $c = 1 + \mu_{\rm max}^{-2g}$. This is irreconcilable with $\lambda_{\rm max}= \mu_{\rm max}$ by the observations in the previous paragraph. Therefore $\lambda_{\rm max}\gt \mu_{\rm max}$.

I bet this is known already.

$\endgroup$
1
  • $\begingroup$ Brendan, Thanks very much. I had missed Godsil's result and its significance for my question. $\endgroup$ Jun 13, 2014 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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