Cube-connected circulants: Bisection width, Wiener and forwarding indices

The family of cube-connected circulants has been recently introduced as an efficient model for communication networks. A cube-connected circulant has many favourable features including vertex-transitivity, logarithmic diameter, and recursive construction in general. However, our knowledge about many other characteristics of this family of graphs is limited. In this paper, we compute nearly matching bounds for the Wiener index, total distance, bisection width, vertex- and edge-forwarding indices of cube-connected circulants. Furthermore, we introduce the class of 'partition-proportional graphs'. This gives a more general classification of graphs than the 'orbit proportional' classification in the literature. Then we develop results to obtain bounds for their edge-forwarding index. Using our results, we obtain tight bounds for the edge-forwarding index of cube-connected circulants and multiplicative circulants. We show that cube-connected circulants outperform other well-known network models in terms of maximum network throughput. (C) 2019 Elsevier B.V. All rights reserved.