Chalkboard #11 Maximal Independent Sets, Cycles and Spanning Trees

In graph theory an independent set is a set of vertices in a graph in which no two vertices are adjacent so no edge connects these two vertices. The maximal independent set (MIS) is the largest set of independent sets for a graph. An MIS is not a subset of any independent set.

The number of maximal independent sets for an n-cycle or an n-gon graph can be found from the Perrin sequence of numbers.

Reference: R. Bisdorff and JL. Marichal, Counting non-isomorphic maximal independent sets of the n-cycle graph, J. of Integer Sequences, Vol. 11 (2008).