VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS

DOI10.1142/S1793830911001115zbMath1222.05199arXiv1008.2897MaRDI QIDQ3087098

Eugen Mandrescu, Vadim E. Levit

Publication date: 2 August 2011

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

triangle-free graph; König-Egerváry graph; greedoid; local maximum stable set; very well-covered graph

Mathematics Subject Classification ID

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

05B35: Combinatorial aspects of matroids and geometric lattices

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs, Local maximum stable set greedoids stemming from very well-covered graphs, Almost unimodal and real-rooted graph polynomials, Approximating maximum uniquely restricted matchings in bipartite graphs

Cites Work

• A characterization of the graphs in which the transversal number equals the matching number
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Well-covered graphs and extendability
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Very well covered graphs
• A new greedoid: The family of local maximum stable sets of a forest
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• Unique Maximum Matching Algorithms
• Complexity results for well‐covered graphs
• Introduction to Greedoids
• Vertex packings: Structural properties and algorithms
• Some covering concepts in graphs
• Uniquely restricted matchings