Well-covered graphs and extendability

DOI10.1016/0012-365X(94)90253-4zbMath0817.05069OpenAlexW2092749268MaRDI QIDQ1318795

Nathaniel Dean, Jennifer S. Zito

Publication date: 4 April 1994

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

Full work available at URL: https://doi.org/10.1016/0012-365x(94)90253-4

zbMATH Keywords

algorithmscharacterizationsextendabilitymaximum independent setwell-covered graph\(k\)-extendable graphsrecognizing well- covered graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Related Items

Strongly well-covered graphs, Recognizing well covered graphs of families with special \(P _{4}\)-components, The structure of well-covered graphs with no cycles of length 4, WELL-COVERED GRAPHS: A SURVEY, The well-covered dimension of random graphs, 1-extendability of independent sets, Recognizing well-dominated graphs is coNP-complete, Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\), Computing well-covered vector spaces of graphs using modular decomposition, Local maximum stable set greedoids stemming from very well-covered graphs, Graphs vertex-partitionable into strong cliques, Well-covered graphs and factors, 1-extendability of independent sets, On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph, VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS, Mind the independence gap, Excellent graphs with respect to domination: subgraphs induced by minimum dominating sets, Partitions and well-coveredness: the graph sandwich problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering and domination in perfect graphs
• On n-extendable graphs
• On B-graphs
• Independent domination in chordal graphs
• A characterization of well covered graphs of girth 5 or greater
• Matching-perfect and cover-perfect graphs
• Very well covered graphs
• Domination in permutation graphs
• Complexity results for well‐covered graphs
• Matchings in polytopal graphs
• On some subclasses of well-covered graphs
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• Some covering concepts in graphs