Local maximum stable set greedoids stemming from very well-covered graphs

DOI10.1016/j.dam.2012.03.017zbMath1245.05105arXiv1102.1142OpenAlexW1825447571WikidataQ114858906 ScholiaQ114858906MaRDI QIDQ444454

Eugen Mandrescu, Vadim E. Levit

Publication date: 14 August 2012

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

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

zbMATH Keywords

perfect matchingEgerváry graphgreedoidköniglocal maximum stable setvery well-covered graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

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

Cites Work

• A characterization of the graphs in which the transversal number equals the matching number
• On local maximum stable set greedoids
• Greedoids
• Graph operations that are good for greedoids
• A characterization of well covered graphs of girth 5 or greater
• The dependence graph for bases in matroids
• 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
• On 4-connected claw-free well-covered graphs
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• On \(\alpha\)-critical edges in König--Egerváry graphs
• VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS
• Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
• Introduction to Greedoids
• Vertex packings: Structural properties and algorithms
• Well covered simplicial, chordal, and circular arc graphs
• The Clique Corona Operation and Greedoids
• Some covering concepts in graphs
• Uniquely restricted matchings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Local maximum stable set greedoids stemming from very well-covered graphs