A characterization of well-covered graphs in terms of forbidden costable subgraphs
type: Item
instance of: scholarly article
title: A characterization of well-covered graphs in terms of forbidden costable subgraphs
zbMATH Open document ID: 0971.05085
DOI: 10.1007/BF02675790
published in: Mathematical Notes
publication date: 2001-04-02T00:00:00Z
review text: A graph is called well-covered if all maximal independent sets have the same number of vertices. A subgraph of a graph \(G\) is called costable by the author if it is an induced subgraph that results from \(G\) by the deletion of an independent set in \(G\) together with its neighbourhood. So the costable subgraphs of a graph are a subset of its induced subgraphs. The author finds several connections between the class of well-covered graphs and the costable subgraph relation: The class of well-covered graphs is closed under taking costable subgraphs, and it can be described by the `forbidden subgraphs', those graphs never occuring as costable subgraph of a well-covered graph (so it is the maximal class with that set of forbidden subgraphs). He gives a description of a set of forbidden subgraphs generating the well-covered graphs: the joins of several well-covered graphs with distinct independence number. Some consequences are also discussed.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1517719
zbMATH Keywords: well-covered graphs
zbMATH Keywords: maximal independent sets
zbMATH Keywords: costable subgraphs
author: I.È. Zverovich
reviewed by: Peter Brass
MaRDI profile type: Publication
cites work: Q3139761
cites work: Complexity results for well‐covered graphs
cites work: WELL-COVERED GRAPHS: A SURVEY
cites work: A characterization of well covered graphs of girth 5 or greater
cites work: A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
cites work: Q4842756
cites work: On 4-connected claw-free well-covered graphs
full work available at URL: https://doi.org/10.1007/bf02675790
OpenAlex ID: W2004534629
description: scientific article; zbMATH DE number 1517719