Reference : Counting non-isomorphic maximal independent sets of the n-cycle graph
Scientific congresses, symposiums and conference proceedings : Unpublished conference
Physical, chemical, mathematical & earth Sciences : Mathematics
Computational Sciences
http://hdl.handle.net/10993/10987
Counting non-isomorphic maximal independent sets of the n-cycle graph
English
Bisdorff, Raymond mailto [University of Luxembourg > Faculty of Law, Economics and Finance > Applied Mathematics Unit (SMA)]
Marichal, Jean-Luc mailto [University of Luxembourg > Faculty of Law, Economics and Finance > Applied Mathematics Unit (SMA)]
Jan-2007
1
No
No
International
21st Annual Conf. of the Belgian Operational Research Society (ORBEL 21), Luxembourg, Jan. 18-19, 2007
from 18-01-2007 to 19-01-2007
Raymond Bisdorff
Claude Lamboray
Jean-Luc Marichal
Patrick Meyer
Luxembourg
Luxembourg
[en] maximal independent set ; cycle graph ; combinatorial enumeration ; dihedral group ; group action ; cyclic and palindromic composition of integers ; Perrin and Padovan sequences
[en] It is known that the number of maximal independent sets of the $n$-cycle graph $C_n$ is given by 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 unlabelled (i.e., defined up to a rotation) maximal independent sets and the number of unlabelled 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/10987
http://sma.uni.lu/orbel21/

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
orbel21abs.pdfAuthor postprint74.1 kBView/Open

Additional material(s):

File Commentary Size Access
Open access
Transparents.pdfSlides611.01 kBView/Open
Open access
program.pdfProgram144.22 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.