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

DOI10.1016/J.JCTB.2009.05.001zbMATH Open1209.05183arXiv0806.4619OpenAlexW2025871027MaRDI QIDQ965239FDOQ965239

Authors: Cheng Yeaw Ku, William Chen 

Publication date: 21 April 2010

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

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.

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

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

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)

Cites Work

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

Cited In (13)

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