Broadcasting in the Arrowhead Torus

Abstract

The "arrowhead torus" is a hierarchical Cayley graph that we define on the triangular (or "hexavalent") grid. A 3-port wormhole broadcasting protocol is derived first from construction, then improved by using edge-disjoint forests. A store-and-forward broadcasting protocol is derived afterwards, then improved by mixing pipelining and arc-disjoint spanning trees. Costs are given in constant and linear time and compared with lower bounds.