Structural properties of Cayley digraphs with applications to mesh and pruned torus interconnection networks. (English) Zbl 1130.68022
Summary: Despite numerous interconnection schemes proposed for distributed multicomputing, systematic studies of classes of interprocessor networks, that offer speed-cost tradeoffs over a wide range, have been few and far in between. A notable exception is the study of Cayley graphs that model a wide array of symmetric networks of theoretical and practical interest. Properties established for all, or for certain subclasses of, Cayley graphs are extremely useful in view of their wide applicability. In this paper, we obtain a number of new relationships between Cayley (di)graphs and their subgraphs and coset graphs with respect to subgroups, focusing in particular on homomorphism between them and on relating their internode distances and diameters. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes as well as certain classes of pruned tori.
MSC:
| 68M10 | Network design and communication in computer systems |
| 05C20 | Directed graphs (digraphs), tournaments |
| 68M14 | Distributed systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
Cayley digraph; cellular network; coset graph; distributed system; homomorphism; interconnection network; internode distance; diameter; parallel processingReferences:
| [1] | Akers, S. B.; Krishnamurthy, B., A group theoretic model for symmetric interconnection networks, IEEE Trans. Computers, 38, 555-566 (1989) · Zbl 0678.94026 |
| [2] | Annexstein, F.; Baumslag, M.; Rosenberg, A. L., Group action graphs and parallel architectures, SIAM J. Comput., 19, 544-569 (1990) · Zbl 0698.68064 |
| [3] | Biggs, N., Algebraic Graph Theory (1993), Cambridge Univ. Press |
| [4] | M. Heydemann, Cayley graphs and interconnection networks, in: Graph Symmetry: Algebraic Methods and Applications, 1997, pp. 167-224; M. Heydemann, Cayley graphs and interconnection networks, in: Graph Symmetry: Algebraic Methods and Applications, 1997, pp. 167-224 · Zbl 0885.05075 |
| [5] | Kwai, D. M.; Parhami, B., Pruned three-dimensional toroidal networks, Inform. Process. Lett., 68, 179-183 (1998) · Zbl 1339.68207 |
| [6] | Lakshmivarahan, S.; Jwo, J.-S.; Dahl, S. K., Symmetry in interconnection networks based on Cayley graphs of permutation group: A survey, Parallel Computing, 19, 361-401 (1993) · Zbl 0777.05064 |
| [7] | Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann · Zbl 0743.68007 |
| [8] | Miller, M.; Siran, J., Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin., #DS14 (2005) · Zbl 1079.05043 |
| [9] | Nocetti, F. G.; Stojmenovic, I.; Zhang, J., Addressing and routing in hexagonal networks with applications for tracking mobile users and connection rerouting in cellular networks, IEEE Trans. Parallel and Distributed Systems, 13, 963-971 (2002) |
| [10] | Parhami, B., Introduction to Parallel Processing: Algorithms and Architectures (1999), Plenum |
| [11] | Parhami, B.; Kwai, D. M., A unified formulation of honeycomb and diamond networks, IEEE Trans. Parallel Distrib. Systems, 12, 74-80 (2001) |
| [12] | Stojmenovic, I., Honeycomb networks: Topological properties and communication algorithms, IEEE Trans. Parallel Distrib. Systems, 8, 1036-1042 (1997) |
| [13] | Xiao, W.; Parhami, B., Some mathematical properties of Cayley digraphs with applications to interconnection network design, Int. J. Comput. Math., 82, 5, 521-528 (May 2005) · Zbl 1064.05082 |
| [14] | W. Xiao, B. Parhami, Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes, Discrete Appl. Math., in press; W. Xiao, B. Parhami, Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes, Discrete Appl. Math., in press · Zbl 1127.68072 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
