A refined Gallai-Edmonds structure theorem for weighted matching polynomials
type: Item
instance of: scholarly article
title: A refined Gallai-Edmonds structure theorem for weighted matching polynomials
author: Thomás Jung Spier
published in: Discrete Mathematics
publication date: 2023-01-17T00:00:00Z
full work available at URL: https://arxiv.org/abs/2006.15215
review text: In the present paper, the author considers weighted matching polynomials and provides a refinement of the Gallai-Edmonds structure theorem [\textit{J. Edmonds}, Can. J. Math. 17, 449--467 (1965; Zbl 0132.20903); \textit{T. Gallai}, Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 373--395 (1964; Zbl 0144.23204)] by \textit{C. Y. Ku} and \textit{K. B. Wong}, [Linear Algebra Appl. 439, No. 11, 3387--3411 (2013; Zbl 1282.05070)] with a simpler proof. To state the main results, some definitions are first needed. Let \(G\) be a graph. A matching in \(G\) is a set of pairwise non-adjacent edges and the set of all matchings of \(G\) will be denoted by \(\mathcal{M}_G\). If a vertex \(i\) of the graph is not covered by a matching \(M\), then we write \(i \notin M\). For the complete graph \(G\) with vertex set \([n]\) let \(x-r_i\) be the variable weights for every vertex \(i \in [n]\) and let \(\lambda_{jk}\) be non-positive weights for each edge \(jk\) in \(G\). The weighted matching polynomial of \(G\) is defined as \[ \mu (G)(x) = \sum_{M \in \mathcal{M}_G} \prod_{i \notin M} (x-r_i) \prod_{jk \in M} \lambda_{jk}. \] By the Heilmann-Lieb theorem, [\textit{O. J. Heilmann} and \textit{E. H. Lieb}, Commun. Math. Phys. 25, 190--232 (1972; Zbl 0228.05131)] it follows that all the zeros of \(\mu(G)\) are real. So let \(\theta\) be a real number and \(m_{\theta}(G)\) the multiplicity of \(\theta\) as a zero of \(\mu(G)\). Moreover, a vertex \(i\) of \(G\) is called \(\theta\)-essential if \(m_{\theta}(G \setminus i) = m_{\theta}(G) - 1\). Denote by \(D_{\theta,G}\) the set of all \(\theta\)-essential vertices of \(G\) and let \(A_{\theta,G}\) be the set of vertices which are not in \(D_{\theta,G}\) but have a neighbour in \(D_{\theta,G}\). As the main result of the paper, the following stability lemma is proved. It tells us how the matching polynomial changes when a vertex from the set \(A_{\theta,G}\) is deleted. Theorem. If \(i\) is in \(A_{\theta,G}\), then \[ \frac{\mu(G \set…
reviewed by: Niko Tratnik
Mathematics Subject Classification ID: 05C31
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 11A55
zbMATH DE Number: 7643123
zbMATH Keywords: weighted matching polynomial
zbMATH Keywords: Gallai-Edmonds structure theorem
zbMATH Keywords: continued fraction
zbMATH Keywords: Sturm's theorem
MaRDI profile type: Publication
Wikidata QID: Q122417721
OpenAlex ID: W3037510684
cites work: Paths, Trees, and Flowers
cites work: Q5520564
cites work: Matchings and walks in graphs
cites work: Q3137758
cites work: Algebraic matching theory
cites work: On the theory of the matching polynomial
cites work: Theory of monomer-dimer systems
cites work: Q3889331
cites work: Q3516432
cites work: An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial
cites work: Extensions of barrier sets to nonzero roots of the matching polynomial
cites work: Generalized \(D\)-graphs for nonzero roots of the matching polynomial
cites work: Properties of \(\theta\)-super positive graphs
cites work: Gallai-Edmonds structure theorem for weighted matching polynomial
cites work: Generalizing Tutte's theorem and maximal non-matchable graphs
cites work: Q3395507
cites work: Interlacing families. I: Bipartite Ramanujan graphs of all degrees
cites work: Q3241331
cites work: Q3715122
DOI: 10.1016/J.DISC.2022.113244
description: scientific article; zbMATH DE number 7643123