1.Previous
3.Next

Every graph contains at most 3^n/3 maximal independent sets, but many graphs have far fewer.The number of maximal independent sets in n-vertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in n-vertex path graphs is given by the Padovan sequence. Therefore, both numbers are proportional to powers of 1.324718..., the plastic ratio.

1.Previous
3.Next