An Analogue of the Gallai-Edmonds Structure Theorem for Nonzero Roots of the Matching Polynomial

Simple item page
dc.creatorKu, Cheng Yeaw
dc.creatorChen, William
dc.date2008-06-27
dc.date.accessioned2026-07-07T09:47:19Z
dc.date.available2026-07-07T09:47:19Z
dc.descriptionGodsil 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 $θ$ 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.
dc.identifierhttps://arxiv.org/abs/0806.4619
dc.identifierhttp://arxiv.org/abs/0806.4619
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/163833
dc.subjectCombinatorics
dc.titleAn Analogue of the Gallai-Edmonds Structure Theorem for Nonzero Roots of the Matching Polynomial
dc.typetext

Files

Collections

arXiv