School Seminars and Colloquia

Gossiping and routing in second-kind Frobenius graphs

Discrete Structures and Algorithms (Seminar)

by A/Prof Sanming Zhou


Institution: Department of Mathematics and Statistics, The University of Melbourne
Date: Tue 25th May 2010
Time: 2:15 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

Abstract: Two kinds of Cayley graphs associated with finite Frobenius groups exhibit interesting routing properties, making them attractive candidates (at least in theory) for modelling interconnection networks.
In this talk I will focus on gossiping and routing in second-kind Frobenius graphs. In the case when the kernel of the Frobenius group
involved is abelian of odd order, we find the exact value of the minimum gossiping time for such a graph under the store-and-forward, all-port and full-duplex model and prove that the graph admits optimal
gossiping schemes with the following properties: messages are always
transmitted along shortest paths; each arc is used exactly once at each time step; at each step after the initial one the arcs carrying the message originated from a given vertex form a perfect matching. In the case when the kernel of the Frobenius group is abelian of even order, we give an upper bound on the minimum gossiping time under the same model. As examples we will discuss a family of second-kind
Frobenius graphs which contains all Paley graphs and connected generalized Paley graphs.

This talk is based on joint work with Xin Gui Fang at Peking University.

For More Information: contact: David Wood. email: woodd@unimelb.edu.au