Algebraic matching theory
Summary: The number of vertices missed by a maximum matching in a graph \(G\) is the multiplicity of zero as a root of the matchings polynomial \(\mu(G, x)\) of \(G\), and hence many results in matching theory can be expressed in terms of this multiplicity. Thus, if \(\text{mult}(\theta, G)\) denotes the multiplicity of \(\theta\) as a zero of \(\mu(G, x)\), then Gallai's lemma is equivalent to the assertion that if \(\text{mult}(\theta, G\backslash u)< \text{mult}(\theta, G)\) for each vertex \(u\) of \(G\), then \(\text{mult}(\theta, G)= 1\). This paper extends a number of results in matching theory to results concerning \(\text{mult}(\theta, G)\), where \(\theta\) is not necessarily zero. If \(P\) is a path in \(G\) then \(G\backslash P\) denotes the graph got by deleting the vertices of \(P\) from \(G\). We prove that \(\text{mult}(\theta, G\backslash P)\geq \text{mult}(\theta, G)- 1\), and we say \(P\) is \(\theta\)-essential when equality holds. We show that if all paths in \(G\) are \(\theta\)-essential, then \(\text{mult}(\theta, G)= 1\). We define \(G\) to be \(\theta\)-critical if all vertices in \(G\) are \(\theta\)- essential and \(\text{mult}(\theta, G)= 1\). We prove that if \(\text{mult}(\theta, G)= k\) then there is an induced subgraph \(H\) with exactly \(k\) \(\theta\)-critical components, and the vertices in \(G\backslash H\) are covered by \(k\) disjoint paths.
- An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial
- Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
- 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
- The independence number of the strong product of cycles
- Extending the characteristic polynomial for characterization of C\(_{20}\) fullerene congeners
- Null decomposition of trees
- Improved lower bound on the Shannon capacity of C₇
- Lower bounds on matching energy of graphs
- Atoms of the matching measure
- A refined Gallai-Edmonds structure theorem for weighted matching polynomials
- On matching integral graphs
- Graphs with six distinct matching roots
- Maximum multiplicity of a root of the matching polynomial of a tree and minimum path cover
- Gallai-Edmonds structure theorem for weighted matching polynomial
- The acyclic matrices with a P-set of maximum size
- Trace-minimal graphs and D-optimal weighing designs
- Graphs with few matching roots
- Generalizing Tutte's theorem and maximal non-matchable graphs
- Properties of \(\theta\)-super positive graphs
- scientific article; zbMATH DE number 2140696 (Why is no real title available?)
- Graphs whose certain polynomials have few distinct roots
- THE MULTIPLICITY OF ZERO ROOTS OF MATCHING POLYNOMIAL OF A GRAPH
- Matching Energy of Graphs with Maximum Degree at Most 3
- Extensions of barrier sets to nonzero roots of the matching polynomial
- On the number of P-vertices of some graphs
- Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
- Generalized \(D\)-graphs for nonzero roots of the matching polynomial
- A sheaf-theoretic approach to pattern matching and related problems
- Matching integral graphs with maximum vertex degree four
- The P-vertex problem for symmetric matrices whose associated graphs admit perfect matchings
- New families of trees determined by their spectra
- Eigenvalues of universal covers and the matching polynomial
- On the multiplicities of eigenvalues of a Hermitian matrix whose graph is a tree
- An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial
This page was built for publication: Algebraic matching theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1804180)
