FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
Alison Thomson, Sawing Zhou
JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY | CAMBRIDGE UNIV PRESS | Published : 2008
A first kind Frobenius graph is a Cayley graph Cay(K,S) on the Frobenius kernel of a Frobenius group $K \rtimes H$ such that S=a H for some a∈K with 〈aH〉=K, where H is of even order or a is an involution. It is known that such graphs admit 'perfect' routing and gossiping schemes. A circulant graph is a Cayley graph on a cyclic group of order at least three. Since circulant graphs are widely used as models for interconnection networks, it is thus highly desirable to characterize those which are Frobenius of the first kind. In this paper we first give such a characterization for connected 4-valent circulant graphs, and then describe optimal routing and gossiping schemes for those which..View full abstract
Alison Thomson was supported by a Postgraduate Award of the Australian Government. Sanming Zhou was supported by a Discovery Project Grant of the Australian Research Council.