On 4-valent Frobenius circulant graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2012

On 4-valent Frobenius circulant graphs

Résumé

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.
Fichier principal
Vignette du fichier
2024-7502-2-PB.pdf (331.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00990596 , version 1 (13-05-2014)

Identifiants

Citer

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

Collections

TDS-MACS
53 Consultations
770 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More