Gallai-Edmonds Structure Theorem for Weighted Matching Polynomial

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:

34 pages, 5 figures

References in corpus (1)

• Generalized $D$-graphs for Nonzero Roots of the Matching Polynomial