Complete Rotations in Cayley Graphs

Authors: Heydemann M-C.¹; Marlin N.²; Pérennes S.²

Source: European Journal of Combinatorics, Volume 22, Number 2, February 2001 , pp. 179-196(18)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

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 investigate 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. Copyright 2001 Academic Press

Language: English

Document Type: Research article

Affiliations: 1: LRI, URA 410 CNRS, bât 490, Univ. Paris Sud, Orsay Cedex, 91405, France 2: Projet Mascotte (INRIA-CNRS-UNSA), I3S, Univ. Nice-Sophia Antipolis, Sophia Antipolis Cedex, BP 93 06902, France

Publication date: 2001-02-01