𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Routing in a Class of Cayley Graphs of Semidirect Products of Finite Groups

✍ Scribed by Fen Lin Wu; S. Lakshmivarahan; S.K. Dhall

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
374 KB
Volume
60
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

Recently, Draper initiated the study of interconnection networks based on Cayley graphs of semidirect products of two cyclic groups called supertoroids. Interest in this class of graphs stems from their relatively smaller diameter compared to toroids of the same size. The Borel graphs introduced by Arden and Tang are a family of Cayley graphs based on a special class of matrix groups. In this paper, we describe a deterministic, distributed routing scheme for supertoroids. While we do not have a proof of correctness of our scheme, experimental evidence leads to a natural conjecture that our scheme is a shortest path routing algorithm. By proving the similarities among supertoroids, Borel graphs, and metacyclic graphs, this routing scheme is then extended to Borel graphs.

πŸ“œ SIMILAR VOLUMES

Neighbourhood Graphs of Cayley Graphs fo
Neighbourhood Graphs of Cayley Graphs for Finitely-generated Groups
✍ Markus Neuhauser πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 134 KB

In this short note the neighbourhood graph of a Cayley graph is considered. It has, as nodes, a symmetric generating set of a finitely-generated group . Two nodes are connected by an edge if one is obtained from the other by multiplication on the right by one of the generators. Two necessary conditi

Circuits in cayley digraphs of finite ab
Circuits in cayley digraphs of finite abelian groups
✍ Anne Marie Wilkinson πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 290 KB

## Abstract We find all possible lengths of circuits in Cayley digraphs of two‐generated abelian groups over the two‐element generating sets and over certain three‐element generating sets.

On Embeddability into a Semidirect Produ
On Embeddability into a Semidirect Product of a Band by a Group
✍ Bernd Billhardt πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 184 KB

An example of an E-unitary regular semigroup is presented which is not embeddable into a semidirect product of a band by a group. This solves an w embeddability problem raised by M. B. Szendrei in Proc. Roy. Soc. Edinburgh Ž . Ž . x 106 A 1987 , 89᎐102 .

Mutually Permutable Products of Finite G
Mutually Permutable Products of Finite Groups
✍ A. Ballester-Bolinches; M.D. PΓ©rez-Ramos; M.C. Pedraza-Aguilera πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 76 KB
On Non-Cayley Vertex-Transitive Graphs o
On Non-Cayley Vertex-Transitive Graphs of Order a Product of Three Primes
✍ Mohammad A. Iranmanesh; Cheryl E. Praeger πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 192 KB

This paper completes the determination of all integers of the form pqr (where p, q, and r are distinct primes) for which there exists a vertex-transitive graph on pqr vertices which is not a Cayley graph.