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

DOI10.1007/978-3-642-02029-2_12zbMATH Open1194.05062arXiv0809.0259OpenAlexW1603430498MaRDI QIDQ3655146FDOQ3655146

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 7 January 2010

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

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.

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

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

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)

Cites Work

• Matching theory
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Vertex packings: Structural properties and algorithms
• The dependence graph for bases in matroids
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Uniquely restricted matchings
• 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
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Title not available (Why is that?)
• Generalized subgraph-restricted matchings in graphs
• On \(\alpha\)-critical edges in König--Egerváry graphs
• A new greedoid: The family of local maximum stable sets of a forest
• The Clique Corona Operation and Greedoids

Cited In (3)

• Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
• Title not available (Why is that?)
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings

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)