Journal of Integer Sequences, Vol. 11 (2008), Article 08.5.7

Counting Non-Isomorphic Maximal Independent Sets of the n-Cycle Graph


Raymond Bisdorff
Computer Science and Communications Research Unit
University of Luxembourg
162A, avenue de la Faïencerie
L-1511 Luxembourg
Luxembourg

Jean-Luc Marichal
Mathematics Research Unit
University of Luxembourg
162A, avenue de la Faïencerie
L-1511 Luxembourg
Luxembourg

Abstract:

The number of maximal independent sets of the n-cycle graph Cn is known to be the nth term of the Perrin sequence. The action of the automorphism group of Cn 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.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A000010 A000931 A001608 A008683 A113788 A127682 A127683 A127684 A127685 A127686 A127687 .)

Received May 26 2008; revised version received November 25 2008. Published in Journal of Integer Sequences, December 14 2008.


Return to Journal of Integer Sequences home page