On graphs having maximal independent sets of exactly $t$ distinct cardinalities

Bert L. Hartnell, Douglas F. Rall

Published 2011-10-19Version 1

For a given positive integer t we consider graphs having maximal independent sets of precisely t distinct cardinalities and restrict our attention to those that have no vertices of degree one. In the situation when t is four or larger and the length of the shortest cycle is at least 6t-6, we completely characterize such graphs.