RR-2702 : The Diamond Torus : a Cayley Graph on the {\sl 6}-valent Grid

Abstract : We pursue our analysis of a family of Cayley graphs defined on the { \sl 6}-valent grid from generators and relations and provided with a high level of symmetry. The grid $H = (V,¸E)$ is generated by three families of straight lines. We adopt the {\sl non-isotropic} orientation $N \to S$, $NE \to SW$, $N W \to SE$ and define the system of generators $S ={s_1,¸s_2,¸s_3}$ wh ose elements are the three respective translations. The multiplication on $S$ d efines a group acting on the vertices of $V$ with a basic set of relations. The «diamond torus» is the graph of a finite group generated by superimposing a cyclic relation for each direction. The diamond interconnection network has sev eral important advantages. It has a bounded valence as a grid and the highest a llowed valence for a 2D regular grid. As a Cayley graph, it allows recursive co nstructions 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 appears finally as a good host for embedding subvalent topologies like the usual grid. This paper is the replication of a former presentation of the {\it arrowhead torus} in the isotro pic case.

Résumé : On poursuit l'analyse d'une famille de graphes de Cayley définis sur la grille {\sl 6}-valente à partir de générateurs et de relations et pourvus d'un ha ut degré de symétrie. La grille $H = (V,¸E)$ est engendrée par trois familles de droites. On adopte l'orientation {\sl anisotrope} $N \to S$, $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 d e base. Le «tore en rhombe» est le graphe d'un groupe fini engendré en surimpo sant une relation cyclique sur chaque direction. Le réseau d'interconnexion en r hombe a plusieurs avantages importants. En tant que grille, il est de valence b ornée, la plus haute valence possible pour une grille 2D régulière. En tant que gr aphe de Cayley, il est récursivement constructible et autorise des schémas de typ e diviser-conquérir! pour la dissémination d'information, il est de plus sommet-transitif et tous l es routeurs se comporteront ainsi de la même manière. Par construction, il app araît finalement comme un hôte apte au plongement de topologies subvalentes co mme la grille usuelle. Ce papier est le pendant d'une présentation antérieure du {\it tore en sagette} pour le cas isotrope.

RR-2702 - The Diamond Torus : a Cayley Graph on the {\sl 6}-valent Grid