A characterization of Konig-Egervary graphs using a common property of all maximum matchings

zbMath1274.05402arXiv0911.4626MaRDI QIDQ2857406

Vadim E. Levit, Eugen Mandrescu

Publication date: 1 November 2013

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Related Items (6)

Critical independent sets and König-Egerváry graphs ⋮ The maximum number of maximum dissociation sets in trees ⋮ On maximum matchings in König-Egerváry graphs ⋮ Polynomial time recognition of essential graphs having stability number equal to matching number ⋮ Combinatorial and spectral properties of König-Egerváry graphs ⋮ A characterization of König-Egerváry graphs with extendable vertex covers

Cites Work

• A characterization of the graphs in which the transversal number equals the matching number
• The critical independence number and an independence decomposition
• Ear-decompositions of matching-covered graphs
• Matching theory
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
• Combinatorial properties of the family of maximum stable sets of a graph
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Critical independent sets and König-Egerváry graphs
• On \(\alpha\)-critical edges in König--Egerváry graphs
• Node-weighted graphs having the König-Egerváry property
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Paths, Trees, and Flowers
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A characterization of Konig-Egervary graphs using a common property of all maximum matchings