### On 4-valent Frobenius circulant graphs

*Sanming Zhou*

#### Abstract

A 4-valent first-kind Frobenius circulant graph is a connected Cayley
graph DL

_{n}(1, h) = Cay(ℤ_{n}, H) on the additive group of integers modulo n, where each prime factor of n is congruent to 1 modulo 4 and H={[1], [h], -[1], -[h]} with h a solution to the congruence equation x^{2}+ 1 ≡0 (n). In [A. Thomson and S. Zhou, Frobenius circulant graphs of valency four, J. Austral. Math. Soc. 85 (2008), 269 13;282] it was proved that such graphs admit `perfect' routing and gossiping schemes in some sense, making them attractive candidates for modelling interconnection networks. In the present paper we prove that DL_{n}(1, h) has the smallest possible broadcasting time, namely its diameter plus two, and we explicitly give an optimal broadcasting in DL_{n}(1, h). Using number theory we prove that it is possible to recursively construct larger 4-valent first-kind Frobenius circulants from smaller ones, and we give a methodology for such a construction. These and existing results suggest that, among all 4-valent circulant graphs, 4-valent first-kind Frobenius circulants are extremely efficient in terms of routing, gossiping, broadcasting and recursive construction.Full Text: PDF PostScript