On the number of vertices belonging to all maximum stable sets of a graph

DOI10.1016/S0166-218X(01)00327-4MaRDI QIDQ1850112zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Endre Boros, Martin Charles Golumbic, Vadim E. Levit

Publication date 2 December 2002

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

Full work available at URL https://doi.org/10.1016/s0166-218x(01)00327-4

zbMATH Keywords

maximum matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The number of all stable sets in some classes of graphs
• Maximum stable sets in analogs of Kneser and complete graphs
• scientific article; zbMATH DE number 220408
• Combinatorial properties of the family of maximum stable sets of a graph
• A CHARACTERIZATION OF STABLE GRAPHS ON A MAXIMUM(MINIMUM) NUMBER OF EDGES
• Stable sets of maximal size in Kneser-type graphs
• On graphs whose maximal cliques and stable sets intersect
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• scientific article; zbMATH DE number 1792601
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Graphs whose vertex independence number is unaffected by single edge addition or deletion
• On Representatives of Subsets
• The ellipsoid method and its consequences in combinatorial optimization
• The structure and maximum number of maximum independent sets in trees
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph

Cited in

(46)

• A shy invariant of graphs
• A set and collection lemma
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The number of all stable sets in some classes of graphs
• Combinatorial and spectral properties of König-Egerváry graphs
• Two more characterizations of König-Egerváry graphs
• Crown reductions for the minimum weighted vertex cover problem
• Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
• On vertex orderings and the stability number in triangle-free graphs
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• On an annihilation number conjecture
• Smaller parameters for vertex cover kernelization
• On König-Egerváry collections of maximum critical independent sets
• Fixed cardinality stable sets
• On some conjectures concerning critical independent sets of a graph
• On the vertices belonging to all, some, none minimum dominating set
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• On critical difference, independence number and matching number of graphs
• scientific article; zbMATH DE number 5781390 (Why is no real title available?)
• The intersection of all maximum stable sets of a tree and its pendant vertices
• On \(\alpha\)-critical edges in König--Egerváry graphs
• Polynomially solvable cases for the maximum stable set problem
• On almost bipartite non-König-Egerváry graphs
• On local maximum stable set greedoids
• A CHARACTERIZATION OF STABLE GRAPHS ON A MAXIMUM(MINIMUM) NUMBER OF EDGES
• Stable sets of maximal size in Kneser-type graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• On the critical difference of almost bipartite graphs
• On vertices contained in all or in no metric basis
• Critical and maximum independent sets of a graph
• On 1-König-Egerváry graphs
• On the Kőnig-Egerváry index of a graph
• On the intersection of all critical sets of a unicyclic graph
• scientific article; zbMATH DE number 220408 (Why is no real title available?)
• A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
• Combinatorial properties of the family of maximum stable sets of a graph
• Optimal monotone relabelling of partially non-monotone ordinal data
• On maximum matchings in König-Egerváry graphs
• Monotonic properties of collections of maximum independent sets of a graph
• Polynomial time recognition of essential graphs having stability number equal to matching number
• Stable sets versus independent sets
• New results relating independence and matchings
• The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
• On König-Egerváry corona graphs
• Regular graphs with equal matching number and independence number
• The independence polynomial of trees is not always log-concave starting from order 26

This page was built for publication: On the number of vertices belonging to all maximum stable sets of a graph

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