An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial

DOI10.1016/J.JCTB.2009.05.001MaRDI QIDQ965239zbMATH OpenOpenAlexFDO

Authors Cheng Yeaw Ku, William Chen

Publication date 21 April 2010

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0806.4619

zbMATH Keywords

matching polynomialvertex transitive graphGallai-Edmonds structure theorem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 $heta$ 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.

Recommendations

• Algebraic matching theory
• Gallai-Edmonds structure theorem for weighted matching polynomial
• A refined Gallai-Edmonds structure theorem for weighted matching polynomials
• scientific article; zbMATH DE number 2140696
• Generalizing Tutte's theorem and maximal non-matchable graphs

Cites work

• Algebraic matching theory
• Matching theory
• Problems in algebraic combinatorics
• The second largest eigenvalue of a tree
• Theory of monomer-dimer systems

Cited in

(13)

• Extensions of barrier sets to nonzero roots of the matching polynomial
• Atoms of the matching measure
• On matching integral graphs
• Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
• On the location of zeros of the Laplacian matching polynomials of graphs
• Graphs with few matching roots
• Gallai-Edmonds structure theorem for weighted matching polynomial
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• A refined Gallai-Edmonds structure theorem for weighted matching polynomials
• Generalized \(D\)-graphs for nonzero roots of the matching polynomial
• THE MULTIPLICITY OF ZERO ROOTS OF MATCHING POLYNOMIAL OF A GRAPH
• Generalizing Tutte's theorem and maximal non-matchable graphs
• Further results on the largest matching root of unicyclic graphs

This page was built for publication: An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q965239)