School Seminars and Colloquia

Frobenius graphs as interconnection networks

School Seminar

by Alison Thomson

Institution: Department of Mathematics and Statistics
Date: Tue 16th June 2009
Time: 12:00 PM
Location: Russell Love Theatre, Richard Berry Building

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.