On \(\alpha\)-critical edges in König--Egerváry graphs

DOI10.1016/j.disc.2006.05.001zbMath1102.05050OpenAlexW1493119590MaRDI QIDQ2502896

Vadim E. Levit, Eugen Mandrescu

Publication date: 13 September 2006

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2006.05.001

zbMATH Keywords

treebipartite graphcoremaximum matchingmaximum stable set

Mathematics Subject Classification ID

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

Related Items (9)

On the critical difference of almost bipartite graphs ⋮ Critical independent sets and König-Egerváry graphs ⋮ A set and collection lemma ⋮ Local maximum stable set greedoids stemming from very well-covered graphs ⋮ On maximum matchings in König-Egerváry graphs ⋮ Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids ⋮ A characterization of Konig-Egervary graphs using a common property of all maximum matchings ⋮ On the intersection of all critical sets of a unicyclic graph ⋮ On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of the graphs in which the transversal number equals the matching number
• Matching theory
• The uniquely solvable bipartite matching problem
• 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 the number of vertices belonging to all maximum stable sets of a graph
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• On the uniqueness of perfect matchings in bipartite graphs
• On the critical lines of a graph
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• The structure and maximum number of maximum independent sets in trees

This page was built for publication: On \(\alpha\)-critical edges in König--Egerváry graphs