A FEW FAMILIES OF CAYLEY GRAPHS AND THEIR EFFICIENCY AS COMMUNICATION NETWORKS
Hamid Mokhtar · Bulletin of the Australian Mathematical Society · 2017
Cayley graphs are highly attractive structures for communication networks because of their many desirable properties, including vertex-transitivity and efficient routing algorithms [4].The families of circulants and cube-connected graphs are among the most popular Cayley graphs for efficient communication networks [11,12].The diameter, forwarding and optical indices, bisection width and Wiener index of a network are among the most important parameters to measure the efficiency of the network [2,[5][6][7].Circulant graphs and, in particular, circulant graphs with small degrees are interesting models for communication networks [1].However, our knowledge of many of their parameters, including the arc-forwarding index, edge-forwarding index, directed and undirected optical indices, are very limited, except for very few special cases.We study the family of circulant graphs of degree 4 and obtain lower and upper bounds for their forwarding and optical indices.We give approximation algorithms for the corresponding problems of the forwarding indices and optical indices with a small constant performance ratio.Our results on the family of circulant graphs of degree 4 are published in [3].The family of recursive cubes of rings has received a lot of attention for communication networks [10], but many aspects of them have remained unknown.We study this family of graphs by redefining each of them as a Cayley graph on the semidirect product of an elementary abelian group by a cyclic group in order to facilitate the study of them by using algebraic tools.We give an algorithm for computing shortest paths and obtain the exact value of their diameters.We obtain