𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complete Rotations in Cayley Graphs

✍ Scribed by Marie-Claude Heydemann; Nausica Marlin; Stéphane Pérennes

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
220 KB
Volume
22
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Isomorphic factorization of the complete
Isomorphic factorization of the complete graph into Cayley digraphs
✍ G. L. Chia; Poh-Hwa Ong 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

## Abstract Let __Z__~__p__~ denote the cyclic group of order __p__ where __p__ is a prime number. Let __X__ = __X__(__Z__~__p__~, __H__) denote the Cayley digraph of __Z__~__p__~ with respect to the symbol __H__. We obtain a necessary and sufficient condition on __H__ so that the complete graph on

Rotation numers for complete bipartite g
Rotation numers for complete bipartite graphs
✍ Julie Haviland; Andrew Thomason 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 510 KB

## Abstract A __rooted graph__ is a pair (__G, x__) where __G__ is a simple undirected graph and __x__ ϵ __V__(__G__). If __G__ if rooted at __x__, then its __rotation number h(G, x)__ is teh minimum number of edges in a graph __F__, of the same order as __G__, such that for all __v__ ϵ __V(F)__ we

Hamiltonian cycles in cayley color graph
Hamiltonian cycles in cayley color graphs
✍ Joseph B. Klerlein 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 1 views

## Abstract A group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph __D__~Δ~(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are

Small cutsets in quasiminimal Cayley gra
Small cutsets in quasiminimal Cayley graphs
✍ Y.O. Hamidoune; A.S. Lladó; O. Serra 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 586 KB

We continue the recent study carried out by several authors on the cut sets in Cayley graphs with respect to quasiminimal generating sets. We improve the known results on these questions. The application of our main theorem to symmetric Cayley graphs on minimal generating sets leads to the followin

More rotation numbers for complete bipar
More rotation numbers for complete bipartite graphs
✍ Béla Bollobás; E. J. Cockayne 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB

## Abstract Let __G__ be a simple undirected graph which has __p__ vertices and is rooted at __x__. Informally, the __rotation number h(G, x)__ of this rooted graph is the minimum number of edges in a __p__ vertex graph __H__ such that for each vertex __v__ of __H__, there exists a copy of __G__ in