On some subclasses of well‐covered graphs

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.