Skip to Main content Skip to Navigation
Journal articles

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 x 2 + 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 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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00990596
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 4:27:53 PM
Last modification on : Thursday, September 7, 2017 - 1:03:38 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:32:22 PM

File

2024-7502-2-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990596, version 1

Collections

Citation

Sanming Zhou. On 4-valent Frobenius circulant graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.173--188. ⟨hal-00990596⟩

Share

Metrics

Record views

228

Files downloads

808