On some subclasses of well‐covered graphs
Jo Ann W. Staples · Journal of Graph Theory · 1979
Abstract 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 Wn property: For a positive integer n, a graph G belongs to class Wn 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 Wn graphs containing arbitrarily large independent sets. A characterization of Wn 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 Wn graphs.