Unpublished conference/Abstract (Scientific congresses, symposiums and conference proceedings)
Counting non-isomorphic maximal independent sets of the n-cycle graph
Bisdorff, Raymond; Marichal, Jean-Luc
200721st Annual Conf. of the Belgian Operational Research Society (ORBEL 21), Luxembourg, Jan. 18-19, 2007
 

Files


Full Text
orbel21abs.pdf
Author postprint (75.88 kB)
Download
Annexes
Transparents.pdf
(625.68 kB)
Slides
Download
program.pdf
(147.68 kB)
Program
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
maximal independent set; cycle graph; combinatorial enumeration; dihedral group; group action; cyclic and palindromic composition of integers; Perrin and Padovan sequences
Abstract :
[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.
Disciplines :
Mathematics
Author, co-author :
Bisdorff, Raymond ;  University of Luxembourg > Faculty of Law, Economics and Finance > Applied Mathematics Unit (SMA)
Marichal, Jean-Luc ;  University of Luxembourg > Faculty of Law, Economics and Finance > Applied Mathematics Unit (SMA)
External co-authors :
no
Language :
English
Title :
Counting non-isomorphic maximal independent sets of the n-cycle graph
Publication date :
January 2007
Number of pages :
1
Event name :
21st Annual Conf. of the Belgian Operational Research Society (ORBEL 21), Luxembourg, Jan. 18-19, 2007
Event organizer :
Raymond Bisdorff
Claude Lamboray
Jean-Luc Marichal
Patrick Meyer
Event place :
Luxembourg, Luxembourg
Event date :
from 18-01-2007 to 19-01-2007
Audience :
International
Focus Area :
Computational Sciences
Name of the research project :
Recherches méthodologiques et mathématiques en aide à la décision et à la classification > 01/01/2005 – 12/12/2007 > BISDORFF Raymond
Funders :
University of Luxembourg - UL
Available on ORBilu :
since 16 November 2013

Statistics


Number of views
55 (8 by Unilu)
Number of downloads
485 (2 by Unilu)

Bibliography


Similar publications



Contact ORBilu