A characterization of certain families of well-covered circulant graphs

Abstract

A graph G is said to be well-covered if every maximal independent set is a maximum independent set. The concept of well-coveredness is of interest due to the fact that determining the independence number of an arbitrary graph is NP- complete, and yet for a well-covered graph it can be established simply by finding any one maximal independent set. A circulant graph C (n,S) is defined for a positive integer n and a subset S of the integers 1, 2, …, [n/2], called the connections. The vertex set is Z[subscript n], the integers modulo n. There is an edge joining two vertices j and i if and only if the difference |j-i| is in the set S. In this thesis, we investigate various families of circulant graphs. Though the recognition problem for well-covered circulant graphs is co-NP-complete, we are able to determine some general properties regarding these families and to obtain a characterization.