Frobenius graphs as interconnection networks
by Alison Thomson
Abstract: Frobenius graphs are highly symmetric, making them an attractive architecture for use in parallel computing. In particular, they admit routing and gossiping schemes which are perfectly efficient. They are so named because they are orbital graphs of a Frobenius group.
Using elementary techniques from group theory and number theory, we classify a large class of first-kind Frobenius circulant graphs. Circulants of low degree are of particular interest for practical applications, and we examine these in more detail. For first-kind Frobenius circulants of degree four, we give formulas for diameter and edge-forwarding index, using a geometric representation as a labelled integer lattice.
We show that the degree six circulants of maximum order for a given diameter are Frobenius graphs, and we show that first-kind Frobenius circulants of degree six can be represented as a tessellation of labelled hexagons.
Finally, we demonstrate that ``perfect" gossiping in first-kind Frobenius graphs is possible in a variety of modes, including full-duplex, half-duplex, and restricted port modes.