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

Abstract : The «arrowhead torus» is a broadcast graph that we define on the {\sl 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 {\sl 6}-valent grid $H = (V,¸E)$ is generated by three families of straight lines. We adopt the isotropic orientation $S \to N$, $NE \to SW$, $NW \to 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 {\it 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.

Résumé : Le tore dit en «sagette» (ou encore «en pointe-de-flèche») est un graphe de diffusion que l'on définit sur la grille {\sl 6}-valente comme graphe de Cayley. Le terme est emprunté à Mandelbrot qui qualifie de cette façon l'une des célèbres constructions fractales de Sierpinski. La grille {\sl 6}-valente $H = (V,¸E)$ est engendrée par trois familles de droites. On adopte l'orientation isotrope $S \to N$, $NE \to SW$, $NW \to SE$ et on définit le système de générateurs $S ={s_1,¸s_2,¸s_3}$ dont les éléments sont les trois translations respectives. La multiplication sur $S$ définit un groupe opérant sur les sommets de $V$ selon un ensemble de relations de base. La {\it sagette} est le graphe d'un groupe fini engendré en surimposa- nt une relation cyclique sur chaque direction. Le réseau d'interconnexion en sagette a plusieurs avantages importants. En tant que grille, il est de valence bornée, la plus haute valence possible pour une grille 2D régulière- . En t! ant que graphe de Cayley, il est récursivement constructible et autorise des schémas de type diviser-conquérir pour la dissémination d'information, il est de plus sommet-transitif et tous les routeurs se comporteront ainsi de la même manière. Par construction, il apparaitra finalement comme un hôte apte au plongement de topologies subvalentes comme la grille usuelle.

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