## Matching polynomials of vertex transitive graphs

Let G be a graph of order *n*. Denote by p(G,*k*) the number of *k*-matchings in G.
The * matching polynomial * of G is defined as

μ(G,*x*) = Σ (-1)^{k}
p(G,*k*) * x*^{n-2k}

where the sum runs from 0 to [*n*/2]. It is known that every matching polynomial has only real roots. See
[1,2].

Some time ago I made the following

**Conjecture:**
For every integer * r* there exists a vertex transitive graph
G whose matching polynomial has a root of multiplicity at least *r*.

It would be interesting to find a vertex transitive graph whose matching
polynomial has a nonsimple root. Such a graph would not have a hamiltonian path
(see [1,2]) and would disprove a conjecture of Lovasz that every vertex
transitive graph has a hamiltonian path.

**
****References:**

[1] Heilmann, Ole J.; Lieb, Elliott H. Theory of monomer-dimer systems.
Comm. Math. Phys. 25 (1972), 190-232.

[2] Godsil, C. D.; Gutman, I. On the theory of the matching polynomial.
J. Graph Theory 5 (1981), 137-144.

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: junij 15, 2001.