##
**
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
*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.

**
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**