Counting non-isomorphic maximal independent sets of the n-cycle graph

Details Counting non-isomorphic maximal independent sets of the n-cycle graph Counting non-isomorphic maximal independent sets of the n-cycle graph

2007-01-23

arxiv.org/abs/math/0701647v2

Journal of Integer Sequences 11 (5) (2008), Article 08.5.7

Mathematics

Combinatorics

Revised version

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Counting non-isomorphic maximal independent sets of the n-cycle graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting non-isomorphic maximal independent sets of the n-cycle graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting non-isomorphic maximal independent sets of the n-cycle graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-206118