Cayley Graphs with Complete Rotations

Marie-Claude Heydemann 1 Nausica Marlin Stéphane Pérennes
1 SLOOP - Simulation, Object Oriented Languages and Parallelism
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : As it is introduced by Bermond, Pérennes, and Kodate and by Fragopoulou and Akl, some Cayley graphs, including most popular models for interconnection networks, admit a special automorphism, called complete rotation. Such an automorphism is often used to derive algorithms or properties of the underlying graph. For example, some optimal gossiping algorithms can be easily designed by using a complete rotation, and the constructions of the best known edge disjoint spanning trees in the toroidal meshes and the hypercubes are based on such an automorphism. Our purpose is to investigat- e such Cayley graphs. We relate some symmetries of a graph with potential algebraic symmetries appearing in its definition as a Cayley graph on a group. In the case of Cayley graphs defined on a group generated by transpositions, we characterize the ones admitting a complete rotation.
Type de document :
RR-3624, INRIA. 1999
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:42:30
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:32:49



  • HAL Id : inria-00073053, version 1



Marie-Claude Heydemann, Nausica Marlin, Stéphane Pérennes. Cayley Graphs with Complete Rotations. RR-3624, INRIA. 1999. 〈inria-00073053〉



Consultations de la notice


Téléchargements de fichiers