Cube-connected circulants: Bisection width, Wiener and forwarding indices
| Autor: | Hamid Mokhtar |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) Logarithm Applied Mathematics Multiplicative function 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Wiener index 01 natural sciences Telecommunications network 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Circulant matrix MathematicsofComputing_DISCRETEMATHEMATICS Mathematics Network model |
| Zdroj: | Discrete Applied Mathematics. 272:48-68 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.03.008 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect