An analogue of the Gallai-Edmonds Structure Theorem for non-zero roots of the matching polynomial

作者：Ku Cheng Yeaw^*; Chen William

来源：Journal of Combinatorial Theory - Series B, 2010, 100(2): 119-127.

DOI：10.1016/j.jctb.2009.05.001

• Gallai-Edmonds Structure Theorem
• Matching polynomial
• Vertex transitive graph

Godsil observed the simple fact that the multiplicity of 0 as a root of the matching polynomial of a graph coincides with the classical notion of deficiency. From this fact he asked to what extent classical results in matching theory generalize, replacing "deficiency" with multiplicity of theta as a root of the matching polynomial. We prove an analogue of the Stability Lemma for any given root, which describes how the matching structure of a graph changes upon deletion of a single vertex. An analogue of Gallai's Lemma follows. Together these two results imply an analogue of the Gallai-Edmonds Structure Theorem. Consequently, the matching polynomial of a vertex transitive graph has simple roots.

• 出版日期2010-3