Reference : Counting non-isomorphic maximal independent sets of the n-cycle graph
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/10993/387
Counting non-isomorphic maximal independent sets of the n-cycle graph
English
Bisdorff, Raymond mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Marichal, Jean-Luc mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
2008
Journal of Integer Sequences
University of Waterloo
11
5
1-16
Yes (verified by ORBilu)
International
1530-7638
Waterloo
Canada
[en] maximal independent set ; cycle graph ; combinatorial enumeration ; dihedral group ; group action ; cyclic and palindromic composition of integers ; Perrin and Padovan sequences
[en] 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.
University of Luxembourg - UL
Researchers ; Professionals ; Students
http://hdl.handle.net/10993/387
https://cs.uwaterloo.ca/journals/JIS/VOL11/Marichal/marichal.html
http://arxiv.org/abs/math/0701647

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
NonIsomorphicMaximalIndependentSets.pdfNo commentaryAuthor postprint179 kBView/Open
Limited access
PV-NonIsomorphicMaximalIndependentSets.pdfPublisher postprint184.59 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.