1
$\begingroup$

Heilman and Lieb had proven that if a graph had $d$ as its maximum vertex degree then the roots of the matching polynomial are bounded from above by $2\sqrt{d-1}$.

Is there a modern exposition of this result? Like some review paper may be which has rederived this result?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

You'll find a different looking approach in my paper: C. D. Godsil, Matchings and walks in graphs, J. Graph Theory, 5, (1981) 285–297. The argument there shows that if $G$ is a graph with maximum valency $k$, then there is a tree $T$ with maximum valency $k$ such that that the matching polynomial of $G$ divides that of $T$. Since for trees, the matching and characteristic polynomials coincide, the bound on zeros of the matching polynomial follows from standard bounds on the spectral radius of a tree.

I would not say that the argument in Heilman and Lieb has suffered due to the passage of time.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I am not able to find the following statement in your paper, "if $G$ is a graph with maximum valency $k$, then there is a tree $T$ with maximum valency $k$ such that that the matching polynomial of $G$ gives that of $T$" - could you kindly point out what there implies this? $\endgroup$
    – user6818
    Commented Mar 23, 2015 at 21:26
  • $\begingroup$ All I see there is that for any graph $G$ there, you construct the "path tree" $T$ such that any pair of vertices $v \in V.G$ and $w \in V.T$ you have that $\frac{ \alpha (G /\ v)}{ \alpha(G)} = \frac{\alpha (T /\ v) }{\alpha(T) }$ $\endgroup$
    – user6818
    Commented Mar 23, 2015 at 21:28
  • $\begingroup$ (this is what the abstract says though your theorem 2.5 is stated with only one vertex $v$!) $\endgroup$
    – user6818
    Commented Mar 23, 2015 at 21:46
  • $\begingroup$ The reason your "following statement" is not in the paper is that it is not true. The paper shows that given a graph $G$ thrre is a tree $T$ such that the matching polynomial of $G$ divides the matching polynomial of $T$. But the matching polynomial of a tree is equal to its characteristic polynomial and the graph and the tree have the same maximum valency, so standard eigenvalue bounds on the tree give the bound on the zeros of matching polynomial of $G$. $\endgroup$
    – Chris Godsil
    Commented Mar 23, 2015 at 23:37
  • $\begingroup$ But the statement I quoted is exactly from your own answer! Thats what was surprising to me. So is there an error in the answer you typed? $\endgroup$
    – user6818
    Commented Mar 24, 2015 at 18:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .