Recursive cubes of rings as models for interconnection networks

DOI10.1016/J.DAM.2016.09.026zbMATH Open1358.05265arXiv1602.07374OpenAlexW2962889938MaRDI QIDQ516899FDOQ516899

Authors: Hamid Mokhtar, Sanming Zhou 

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We study recursive cubes of rings as models for interconnection networks. We first redefine 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 the distance between any two vertices in recursive cubes of rings, and obtain the exact value of their diameters. We obtain sharp bounds on the Wiener index, vertex-forwarding index, edge-forwarding index and bisection width of recursive cubes of rings. The cube-connected cycles and cube-of-rings are special recursive cubes of rings, and hence all results obtained in the paper apply to these well-known networks.

Full work available at URL: https://arxiv.org/abs/1602.07374

Recommendations

• Recursive circulants and their embeddings among hypercubes
• A group-theoretic model for symmetric interconnection networks
• The cube-of-rings interconnection network
• Cube-connected circulants: bisection width, Wiener and forwarding indices
• scientific article; zbMATH DE number 436070

zbMATH Keywords

Cayley graphdiametershortest pathinterconnection networksroutingWiener indexcube-connected cyclesbisection widthedge-forwarding indexrecursive cube of ringsvertex-forwarding index

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Network design and communication in computer systems (68M10)

Cites Work

• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes
• Gossiping and routing in undirected triple-loop networks
• Edge-foreward index of star graphs and other Cayley graphs
• Recursive circulants and their embeddings among hypercubes
• The diameter of the cube-connected cycles
• Title not available (Why is that?)
• A Class of Arc-Transitive Cayley Graphs as Models for Interconnection Networks
• A class of hierarchical graphs as topologies for interconnection networks
• The edge-forwarding index or orbital regular graphs
• On forwarding indices of networks
• Gossiping and routing in second-kind Frobenius graphs
• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• LATIN 2004: Theoretical Informatics
• Forwarding and optical indices of a graph
• Forwarding index of cube-connected cycles
• Efficient collective communciation in optical networks
• A parallel routing algorithm on recursive cube of rings networks employing Hamiltonian circuit Latin square
• A new family of interconnection networks of odd fixed degrees
• The cube-of-rings interconnection network
• The forwarding index of communication networks
• Complexity of the Forwarding Index Problem
• Forwarding indices of consistent routings and their complexity
• Title not available (Why is that?)
• Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem
• Forwarding and optical indices of 4-regular circulant networks

Cited In (11)

• A FEW FAMILIES OF CAYLEY GRAPHS AND THEIR EFFICIENCY AS COMMUNICATION NETWORKS
• Eigenvalues of Cayley graphs
• Routing properties of a recursive interconnection network
• The cube-of-rings interconnection network
• Interconnection Networks Based on a Generalization of Cube-Connected Cycles
• Cube-connected circulants: bisection width, Wiener and forwarding indices
• Title not available (Why is that?)
• On recurrent and recursive interconnection patterns
• Exact vertex forwarding index of the strong product of complete graph and cycle
• Variational networks of cube-connected cycles are recursive cubes of rings
• Using semidirect products of groups to build classes of interconnection networks

This page was built for publication: Recursive cubes of rings as models for interconnection networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516899)