Communication orale non publiée/Abstract (Colloques, congrès, conférences scientifiques et actes)
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
 

Documents


Texte intégral
orbel21abs.pdf
Postprint Auteur (75.88 kB)
Télécharger
Annexes
Transparents.pdf
(625.68 kB)
Slides
Télécharger
program.pdf
(147.68 kB)
Program
Télécharger

Tous les documents dans ORBilu sont protégés par une licence d'utilisation.

Envoyer vers



Détails



Mots-clés :
maximal independent set; cycle graph; combinatorial enumeration; dihedral group; group action; cyclic and palindromic composition of integers; Perrin and Padovan sequences
Résumé :
[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 :
Mathématiques
Auteur, co-auteur :
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)
Co-auteurs externes :
no
Langue du document :
Anglais
Titre :
Counting non-isomorphic maximal independent sets of the n-cycle graph
Date de publication/diffusion :
janvier 2007
Nombre de pages :
1
Nom de la manifestation :
21st Annual Conf. of the Belgian Operational Research Society (ORBEL 21), Luxembourg, Jan. 18-19, 2007
Organisateur de la manifestation :
Raymond Bisdorff
Claude Lamboray
Jean-Luc Marichal
Patrick Meyer
Lieu de la manifestation :
Luxembourg, Luxembourg
Date de la manifestation :
from 18-01-2007 to 19-01-2007
Manifestation à portée :
International
Focus Area :
Computational Sciences
URL complémentaire :
Intitulé du projet de recherche :
Recherches méthodologiques et mathématiques en aide à la décision et à la classification > 01/01/2005 – 12/12/2007 > BISDORFF Raymond
Organisme subsidiant :
University of Luxembourg - UL
Disponible sur ORBilu :
depuis le 16 novembre 2013

Statistiques


Nombre de vues
129 (dont 9 Unilu)
Nombre de téléchargements
646 (dont 2 Unilu)

Bibliographie


Publications similaires



Contacter ORBilu