Gallai-Edmonds structure theorem for weighted matching polynomial

DOI10.1016/J.LAA.2013.09.024MaRDI QIDQ2435543zbMATH OpenOpenAlexFDO

Authors Cheng Yeaw Ku, K. B. Wong

Publication date 19 February 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

characteristic polynomialGallai-Edmonds decompositionHermitian matricesmatching polynomialsParter-Wiener theorem

Mathematics Subject Classification ID

Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper, we prove the Gallai-Edmonds structure theorem for the most general matching polynomial. Our result implies the Parter-Wiener theorem and its recent generalization about the existence of principal submatrices of a Hermitian matrix whose graph is a tree. keywords:

Recommendations

• A refined Gallai-Edmonds structure theorem for weighted matching polynomials
• A theorem on the principal structure for independent matchings
• An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial
• scientific article; zbMATH DE number 3972902
• A Gallai–Edmonds‐type structure theorem for path‐matchings

Cites work

• Algebraic matching theory
• An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial
• An extension of the bivariate chromatic polynomial
• Eigenvalues, multiplicities and graphs
• Extensions of barrier sets to nonzero roots of the matching polynomial
• Generalized \(D\)-graphs for nonzero roots of the matching polynomial
• Generalizing Tutte's theorem and maximal non-matchable graphs
• Hermitian Matrices, Eigenvalue Multiplicities, and Eigenvector Components
• scientific article; zbMATH DE number 3112812 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• Inertia characteristics of self-adjoint matrix polynomials
• Matching polynomials and duality
• Matching theory
• Matchings and walks in graphs
• Maximum multiplicity of a root of the matching polynomial of a tree and minimum path cover
• Maximum multiplicity of matching polynomial roots and minimum path cover in general graphs
• On the Eigenvalues and Eigenvectors of a Class of Matrices
• On the theory of the matching polynomial
• Problems in algebraic combinatorics
• Properties of \(\theta\)-super positive graphs
• Spectral multiplicity and splitting results for a class of qualitative matrices
• The Parter--Wiener Theorem: Refinement and Generalization
• The structure of matrices with a maximum multiplicity eigenvalue
• Theory of monomer-dimer systems

Cited in

(7)

• On the total weight of weighted matchings of segment graphs
• A theorem on the principal structure for independent matchings
• A refined Gallai-Edmonds structure theorem for weighted matching polynomials
• Pairing theorem of graph eigenvalues: its new proof and a generalization
• Generalizing Tutte's theorem and maximal non-matchable graphs
• Eigenvalues of universal covers and the matching polynomial
• An analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial

This page was built for publication: Gallai-Edmonds structure theorem for weighted matching polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2435543)