Counting non-isomorphic maximal independent sets of the n-cycle graph
<|reference_start|>Counting non-isomorphic maximal independent sets of the n-cycle graph: The number of maximal independent sets of the n-cycle graph C_n is known to be the nth term of the Perrin sequence. The action of the automorphism group of C_n on the family of these maximal independent sets partitions this family into disjoint orbits, which represent the non-isomorphic (i.e., defined up to a rotation and a reflection) maximal independent sets. We provide exact formulas for the total number of orbits and the number of orbits having a given number of isomorphic representatives. We also provide exact formulas for the total number of unlabeled (i.e., defined up to a rotation) maximal independent sets and the number of unlabeled maximal independent sets having a given number of isomorphic representatives. It turns out that these formulas involve both Perrin and Padovan sequences.<|reference_end|>
@article{bisdorff2007counting,
    title={Counting non-isomorphic maximal independent sets of the n-cycle graph},
    author={Raymond Bisdorff, Jean-Luc Marichal},
    journal={Journal of Integer Sequences 11 (5) (2008), Article 08.5.7},
    year={2007},
    archivePrefix={arXiv},
    eprint={math/0701647},
    primaryClass={math.CO cs.DM math.GR}
}