Egerv\'{a}ry graphs: Deming decompositions and independence structure

arXiv2205.10598MaRDI QIDQ6399772FDOQ6399772

Authors: P. Mark Kayll, Craig E. Larson 

Publication date: 21 May 2022

Abstract: We leverage an algorithm of Deming [R.W. Deming, Independence numbers of graphs -- an extension of the Koenig-Egervary theorem, Discrete Math., 27(1979), no. 1, 23--33; MR534950] to decompose a matchable graph into subgraphs with a precise structure: they are either spanning even subdivisions of blossom pairs, spanning even subdivisions of the complete graph $K_4$, or a KH{o}nig-Egerv'{a}ry graph. In each case, the subgraphs have perfect matchings; in the first two cases, their independence numbers are one less than their matching numbers, while the independence number of the KE subgraph equals its matching number. This decomposition refines previous results about the independence structure of an arbitrary graph and leads to new results about $alpha$-critical graphs.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

This page was built for publication: Egerv\'{a}ry graphs: Deming decompositions and independence structure

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