Abstract:

Let $G$ be a simple connected graph with $n$ vertices. The matching polynomial of $G$ is given by $\sum_{k=0}^{[n/2]}(-1)^km(G, k)x^{n-2k}$, where $m(G, k)$ is the number of $k$-matchings in $G$ with $0\leq k\leq [n/2]$. Let $\Phi_{n, m}$ be the set of graphs with $n$ vertices and $m$ edges having no even cycles, where $n\leq m\leq \frac{3(n-1)}{2}$. In this paper, four new transformations for comparing the largest roots of matching polynomials are introduced and the graph with the largest root of matching polynomial is characterized among graphs in $\Phi_{n, m}$.

Key words: matching polynomial, the largest root, (n, m)-graph, even cycles