# 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