The Arrowhead Torus : a Cayley Graph on the 6-valent Grid

Dominique Désérable 1
1 API - Parallel VLSI Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : The «arrowhead torus» is a broadcast graph that we define on the 6-valent grid as a Cayley graph. We borrow the term from Mandelbrot who qualifies in that way one of the Sierpinski's famous fractal constructions. The 6-valent grid H = (V,¸E) is generated by three families of straight lines. We adopt the isotropic orientation S-> N, NE -> SW, NW ->SE and define the system of generators S ={s_1,¸s_2,¸s_3} whose elements are the three respective translations. The multiplication on S defines a group acting on the vertices of V with a basic set of relations. The arrowhead is the graph of a finite group generated by superimposing a cyclic relation for each direction. The arrowhead interconn- ection network has several important advantages. It has a bounded valence as a grid and the highest allowed valence for a 2D regular grid. As a Cayley graph, it allows recursive constructions and divide-and-conquer schemes for information dissemination, it is also vertex-transitive hence all routers will behave in a similar way. From construction it will appear finally as a good host for embedding subvalent topologies like the usual grid.
Type de document :
[Research Report] RR-2814, INRIA. 1996
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:58:50
Dernière modification le : vendredi 16 novembre 2018 - 01:28:17
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:08:38



  • HAL Id : inria-00073878, version 1


Dominique Désérable. The Arrowhead Torus : a Cayley Graph on the 6-valent Grid. [Research Report] RR-2814, INRIA. 1996. 〈inria-00073878〉



Consultations de la notice


Téléchargements de fichiers