Combinatorial properties of the family of maximum stable sets of a graph

DOI10.1016/S0166-218X(01)00183-4zbMath0992.05062arXivmath/9912047OpenAlexW1998692692MaRDI QIDQ1348387

Vadim E. Levit, Eugen Mandrescu

Publication date: 15 May 2002

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

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

zbMATH Keywords

matchingstability numbermaximum stable setHall's marriage theoremKönig-Egerváry graphs

Mathematics Subject Classification ID

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

Related Items (21)

On some conjectures concerning critical independent sets of a graph ⋮ Critical sets, crowns and local maximum independent sets ⋮ Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs ⋮ On the critical difference of almost bipartite graphs ⋮ Two more characterizations of König-Egerváry graphs ⋮ Critical sets in bipartite graphs ⋮ Critical and maximum independent sets of a graph ⋮ Critical independent sets and König-Egerváry graphs ⋮ A set and collection lemma ⋮ On upper bounds for the independent transversal domination number ⋮ Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions ⋮ Nullspace vertex partition in graphs ⋮ A characterization of Konig-Egervary graphs using a common property of all maximum matchings ⋮ Problems on matchings and independent sets of a graph ⋮ On \(\alpha\)-critical edges in König--Egerváry graphs ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ The intersection of all maximum stable sets of a tree and its pendant vertices ⋮ On the intersection of all critical sets of a unicyclic graph ⋮ Monotonic properties of collections of maximum independent sets of a graph ⋮ On an annihilation number conjecture

Cites Work

• A characterization of the graphs in which the transversal number equals the matching number
• Graphs whose vertex independence number is unaffected by single edge addition or deletion
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• The structure and maximum number of maximum independent sets in trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Combinatorial properties of the family of maximum stable sets of a graph