A refined Gallai-Edmonds structure theorem for weighted matching polynomials (Q2111908)

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 \setminus i)}{\mu(G \setminus \{ i,j \})}(\theta)=\frac{\mu(G)}{\mu(G \setminus j)}(\theta) \] for every vertex \(j\) different from \(i\). It is interesting that the presented proof uses a relation between matching polynomials and branched continued fractions. To present a version of Sylvester's modification of Sturm's theorem [\textit{J. J. Sylvester}, ``On a remarkable modification of Sturm's theorem'', Philosophical Magazine 1853, 446--456], let \(c: i_1 \rightarrow i_n\) be a Hamiltonian path in a graph \(G\) and let \(-c: i_n \rightarrow i_1\) be the reverse path. If \(\theta\) is a real number, let \(V_c(\theta)\) be the number of positive terms in the set \[ \left \{ \frac{\mu(G )}{\mu(G \setminus i_1)}(\theta), \frac{\mu(G \setminus i_1)}{\mu(G \setminus \{ i_1,i_2 \})}(\theta), \ldots, \frac{\mu(G \setminus \{i_1, \ldots, i_{n-1}\})}{\mu(G \setminus \{ i_1,\ldots,i_{n-1},i_n \})}(\theta) \right \}. \] In addition, the number \(V_{-c}(\theta)\) for the path \(-c\) is defined analogously. The Sylvester theorem reads as follows. Theorem. Both \(V_c(\theta)\) and \(V_{-c}(\theta)\), when defined, are equal to the number of zeros of \(\mu(G)\) in the interval \((-\infty,\theta)\). Finally, some applications are presented in the last part of the paper. In particular, results on the largest zero of weighted matching polynomials are stated.