On duality between local maximum stable sets of a graph and its line-graph

DOI10.1007/978-3-642-02029-2_12MaRDI QIDQ3655146zbMATH OpenOpenAlexFDO

Authors Vadim E. Levit, Eugen Mandrescu

Publication date 7 January 2010

Published in Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: G is a Koenig-Egervary graph provided alpha(G)+ mu(G)=|V(G)|, where mu(G) is the size of a maximum matching and alpha(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G if S is a maximum stable set of the closed neighborhood of S. Nemhauser and Trotter Jr. proved that any local maximum stable set is a subset of a maximum stable set of G. In this paper we demonstrate that if S is a local maximum stable set, the subgraph H induced by the closed neighborhood of S is a Koenig-Egervary graph, and M is a maximum matching in H, then M is a local maximum stable set in the line graph of G.

Recommendations

• Two more characterizations of König-Egerváry graphs
• Combinatorial properties of the family of maximum stable sets of a graph
• Critical independent sets and König-Egerváry graphs
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• On maximum matchings in König-Egerváry graphs

Cites work

• A characterization of the graphs in which the transversal number equals the matching number
• A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
• A new greedoid: The family of local maximum stable sets of a forest
• Generalized subgraph-restricted matchings in graphs
• scientific article; zbMATH DE number 1472162 (Why is no real title available?)
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Matching theory
• On \(\alpha\)-critical edges in König--Egerváry graphs
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• The Clique Corona Operation and Greedoids
• The dependence graph for bases in matroids
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• Uniquely restricted matchings
• Vertex packings: Structural properties and algorithms

Cited in

(3)

• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• scientific article; zbMATH DE number 5781390 (Why is no real title available?)
• Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks

This page was built for publication: On duality between local maximum stable sets of a graph and its line-graph

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