On 4-valent Frobenius circulant graphs
Sanming Zhou
Abstract
A 4-valent first-kind Frobenius circulant graph is a connected Cayley
graph DLn(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 x2 + 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 DLn(1, h) has the smallest
possible broadcasting time, namely its diameter plus two, and we
explicitly give an optimal broadcasting in DLn(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