Premium
On some subclasses of well‐covered graphs
Author(s) -
Staples Jo Ann W.
Publication year - 1979
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190030211
Subject(s) - combinatorics , mathematics , independent set , maximal independent set , disjoint sets , split graph , discrete mathematics , cograph , graph , chordal graph , 1 planar graph
A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well‐covered graphs are classified by the W n property: For a positive integer n , a graph G belongs to class W n if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of W n graphs containing arbitrarily large independent sets. A characterization of W n graphs in terms of well‐covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in W n graphs.