Bounds on the largest root of the matching polynomial (Q1208371)

A \(k\)-matching is a matching in a graph \(G\) with exactly \(k\) edges; if this number is \(p(G,k)\) and \(| V(G)|= n\) then the matching polynomial of \(G\) is defined to be \(\mu(G,x)= \sum_ k(-1)^ k p(G,k)x^{n-2k}\). This paper considers the problem of obtaining bounds on the largest zero \(t(G)\) of the matching polynomial---by a famous result of \textit{O. J. Heilmann} and \textit{E. H. Lieb} [Theory of monomer- dimer systems, Commun. Math. Phys. 25, 190-232 (1972; Zbl 0228.05131)], the zeros of the matching polynomial are all real. A \(k\)-matching in \(G\) is an independent set of size \(k\) in the line graph of \(G\). If the largest eigenvalue of the line graph is \(\lambda\), the authors prove that \(t(G)^ 2> 1+\lambda\). If \(G\) has \(n\) vertices and \(e\) edges, they show that \(t(G)^ 2\geq{4e\over n}-1\). It is also proved that if \(H\) is a subgraph of \(G\) then \(t(H)\leq t(G)\). Remarks: It follows from Theorem 2.5 of the reviewer's paper [``Matchings and walks in graphs'', J. Graph Theory 5, 285-297 (1981; Zbl 0466.05053)], that \(t(G)\) is equal to the spectral radius of a tree constructed from \(G\). This leads to another proof of the last result, and allows eigenvalue bounds on trees to be translated into bounds on \(t(G)\).