A class of arc-transitive cayley graphs as models for interconnection networks

Abstract

We study a class of Cayley graphs as models for interconnection networkS. With focus on efficient communication we prove that for any graph in the class there exists a gossiping protocol which exhibits attractive features, and, moreover, we give an algorithm for constructing such a protocol. In particular, these hold for two important subclasses of graphs, namely, Cayley graphs admitting a complete rotation AND Frobenius graphs of a certain type. For such Frobenius graphs, we obtain the minimum gossip time and give an optimal gossiping protocol under whiC. Messages are transmitted along shortest paths and each arc is used exactl y once at each time step. Moreover, for such Frobenius graphs W..