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.