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

DOI10.1016/J.DAM.2012.03.017zbMATH Open1245.05105arXiv1102.1142OpenAlexW1825447571WikidataQ114858906 ScholiaQ114858906MaRDI QIDQ444454FDOQ444454

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 14 August 2012

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

Abstract: A maximum stable set in a graph G is a stable set of maximum cardinality. S is called a local maximum stable set of G if S is a maximum stable set of the subgraph induced by the closed neighborhood of S. A greedoid (V,F) is called a local maximum stable set greedoid if there exists a graph G=(V,E) such that its family of local maximum stable sets coinsides with (V,F). It has been shown that the family local maximum stable sets of a forest T forms a greedoid on its vertex set. In this paper we demonstrate that if G is a very well-covered graph, then its family of local maximum stable sets is a greedoid if and only if G has a unique perfect matching.

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

Recommendations

• Very well-covered graphs of girth at least four and local maximum stable set greedoids
• On local maximum stable set greedoids
• A new greedoid: The family of local maximum stable sets of a forest
• Graph operations that are good for greedoids
• Greedoids on Vertex Sets of Unicycle Graphs

zbMATH Keywords

perfect matchinggreedoidlocal maximum stable setvery well-covered graphEgerváry graphkönig

Mathematics Subject Classification ID

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

Cites Work

• A characterization of well covered graphs of girth 5 or greater
• Some covering concepts in graphs
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Title not available (Why is that?)
• Introduction to Greedoids
• Vertex packings: Structural properties and algorithms
• Title not available (Why is that?)
• The dependence graph for bases in matroids
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Very well covered graphs
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• Very well-covered graphs of girth at least four and local maximum stable set greedoids
• Uniquely restricted matchings
• A characterization of the graphs in which the transversal number equals the matching number
• Title not available (Why is that?)
• Well covered simplicial, chordal, and circular arc graphs
• On \(\alpha\)-critical edges in König--Egerváry graphs
• Well-covered graphs and extendability
• A new greedoid: The family of local maximum stable sets of a forest
• On 4-connected claw-free well-covered graphs
• Title not available (Why is that?)
• Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some structural properties of very well-covered graphs
• The Clique Corona Operation and Greedoids
• On local maximum stable set greedoids
• Greedoids
• Graph operations that are good for greedoids

Cited In (11)

• Greedoids on vertex sets of \(B\)-joins of graphs
• Title not available (Why is that?)
• On local maximum stable set greedoids
• Critical sets, crowns and local maximum independent sets
• Graph operations that are good for greedoids
• Title not available (Why is that?)
• A new greedoid: The family of local maximum stable sets of a forest
• Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Very well-covered graphs of girth at least four and local maximum stable set greedoids
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444454)