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) xn-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