Geodesic
Counting non-isomorphic maximal independent sets of the \(n\)-cycle graph
Journal of integer sequences, Tome 11 (2008) no. 5
The number of maximal independent sets of the $n$-cycle graph $C_{n}$ is known to be the $n$th 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 the Perrin and Padovan sequences.
Classification : 05C69, 05C38, 05A15, 05A17, 05C25
Keywords: maximal independent set, cycle graph, combinatorial enumeration, dihedral group, group action, cyclic and palindromic composition of integers, Perrin sequence, Padovan sequence 
@article{JIS_2008__11_5_a4,
     author = {Bisdorff,  Raymond and Marichal,  Jean-Luc},
     title = {Counting non-isomorphic maximal independent sets of the \(n\)-cycle graph},
     journal = {Journal of integer sequences},
     year = {2008},
     volume = {11},
     number = {5},
     zbl = {1165.05336},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2008__11_5_a4/}
}
TY  - JOUR
AU  - Bisdorff,  Raymond
AU  - Marichal,  Jean-Luc
TI  - Counting non-isomorphic maximal independent sets of the \(n\)-cycle graph
JO  - Journal of integer sequences
PY  - 2008
VL  - 11
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/JIS_2008__11_5_a4/
LA  - en
ID  - JIS_2008__11_5_a4
ER  - 
%0 Journal Article
%A Bisdorff,  Raymond
%A Marichal,  Jean-Luc
%T Counting non-isomorphic maximal independent sets of the \(n\)-cycle graph
%J Journal of integer sequences
%D 2008
%V 11
%N 5
%U http://geodesic.mathdoc.fr/item/JIS_2008__11_5_a4/
%G en
%F JIS_2008__11_5_a4
Bisdorff,  Raymond; Marichal,  Jean-Luc. Counting non-isomorphic maximal independent sets of the \(n\)-cycle graph. Journal of integer sequences, Tome 11 (2008) no. 5. http://geodesic.mathdoc.fr/item/JIS_2008__11_5_a4/