A characterization of König-Egerváry graphs with extendable vertex covers

DOI10.1016/j.ipl.2020.105964zbMath1447.05175OpenAlexW3021746736MaRDI QIDQ783699

Saket Saurabh, M. S. Ramanujan, Venkatesh Raman

Publication date: 4 August 2020

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2020.105964

zbMATH Keywords

graph algorithmsvertex coversmaximum matchingsKönig-Egerváry graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• The complexity of König subgraph problems and above-guarantee vertex cover
• Matching theory
• A characterization of Konig-Egervary graphs using a common property of all maximum matchings
• Paths, Flowers and Vertex Cover
• TWO THEOREMS IN GRAPH THEORY
• Paths, Trees, and Flowers

This page was built for publication: A characterization of König-Egerváry graphs with extendable vertex covers