On the number of vertices belonging to all maximum stable sets of a graph
From MaRDI portal
Publication:1850112
DOI10.1016/S0166-218X(01)00327-4zbMath1010.05058DBLPjournals/dam/BorosGL02OpenAlexW2063262260WikidataQ59560639 ScholiaQ59560639MaRDI QIDQ1850112
Endre Boros, Vadim E. Levit, Martin Charles Golumbic
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
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (26)
Optimal monotone relabelling of partially non-monotone ordinal data ⋮ On some conjectures concerning critical independent sets of a graph ⋮ New results relating independence and matchings ⋮ On the critical difference of almost bipartite graphs ⋮ On vertices contained in all or in no metric basis ⋮ Two more characterizations of König-Egerváry graphs ⋮ Critical and maximum independent sets of a graph ⋮ A set and collection lemma ⋮ Minimum \(d\)-blockers and \(d\)-transversals in graphs ⋮ On critical difference, independence number and matching number of graphs ⋮ On the vertices belonging to all, some, none minimum dominating set ⋮ On maximum matchings in König-Egerváry graphs ⋮ Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions ⋮ On local maximum stable set greedoids ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Combinatorial and spectral properties of König-Egerváry graphs ⋮ On \(\alpha\)-critical edges in König--Egerváry graphs ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ On König-Egerváry collections of maximum critical independent sets ⋮ The intersection of all maximum stable sets of a tree and its pendant vertices ⋮ On the intersection of all critical sets of a unicyclic graph ⋮ Monotonic properties of collections of maximum independent sets of a graph ⋮ On an annihilation number conjecture ⋮ Regular graphs with equal matching number and independence number ⋮ Smaller Parameters for Vertex Cover Kernelization ⋮ The union of minimal hitting sets: parameterized combinatorial bounds and counting
Cites Work
- Unnamed Item
- Graphs whose vertex independence number is unaffected by single edge addition or deletion
- The ellipsoid method and its consequences in combinatorial optimization
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- The structure and maximum number of maximum independent sets in trees
- On Representatives of Subsets
This page was built for publication: On the number of vertices belonging to all maximum stable sets of a graph
