On 4-valent Frobenius circulant graphs

Abstract

A 4-valent first-kind Frobenius circulant graph is a connected Cayley graph DLn(1,h) = Cay(Zn, 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 x2 + 1 = 0 (mod n). In [A. Thomson and S. Zhou, Frobenius circulant graphs of valency four, J. Austral. Math. Soc. 85(2008), 269-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 DLn(1,h) has the smallest possible broadcasting time, namely its diameter plus two, and we ..