Home » Subject » Graph Theory » Algebraic G.T.
Importance: Medium ✭✭
Author(s): Mohar, Bojan
Subject: Graph Theory
» Algebraic Graph Theory
Keywords: matching polynomial
vertex-transitive
Recomm. for undergrads: no
Posted by: Robert Samal
on: April 12th, 2007
Solved by: Cheng Yeaw Ku and William Chen (see [K])
Conjecture   For every integer $ r $ there exists a vertex transitive graph $ G $ whose matching polynomial has a root of multiplicity at least $ r $.

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 $$ \mu(G, x) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k p(G, k) x^{n-2k} \, . $$ It is known that every matching polynomial has only real roots. See [HL, GG].

It would be interesting to solve the Conjecture even for $ r=2 $, that is to find a vertex transitive graph whose matching polynomial has a nonsimple root. Such a graph would not have a hamiltonian path (see [HL, GG]), thus giving a negative answer to a problem of Lovász.

This conjecture is false.

Definition   Given a graph $ G $ and a root $ \theta $ of $ \mu(G,x) $, a vertex $ u $ of $ G $ is said to be $ \theta $-essential if the multiplicity of $ \theta $ as a root of $ \mu(G\backslash u,x) $ is one less than the multiplicity of $ \theta $ as a root of $ \mu(G,x) $.

In [K], Ku and Chen prove the following analogue of Gallai's Lemma.

Theorem   Let $ G $ be a graph and $ \theta $ be a root of $ \mu(G,x) $. If all vertices of $ G $ are $ \theta $-essential, then $ \theta $ has multiplicity 1 as a root of $ \mu(G,x) $.

Since every graph contains a $ \theta $-essential vertex, all vertices of a vertex-transitive graph are $ \theta $-essential. Thus the matchings polynomial of any vertex-transitive graph has only simple roots.

Bibliography

[HL] O. J. Heilmann, E. H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232. MathSciNet

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

[K] Cheng Yeaw Ku and William Chen, An Analogue of the Gallai-Edmunds Structure Theorem for Nonzero Roots of the Matchings Polynomial (June 2008). Preprint available from arXiv

[M] B. Mohar, Problem of the Month


* indicates original appearance(s) of problem.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options