×

Topological properties of the recursive Petersen architecture. (English) Zbl 0833.68010

Summary: The Petersen graph is gaining popularity as an interconnection network because of its several interesting properties. The recursive Petersen architectures is very compact and has some very interesting topological properties. In this paper, we study its topological properties in detail. Two labeling schemes are suggested. Basic routing and broadcasting have been discussed. The most attractive features are its logarithmic (to the base 10) diameter and high symmetry.

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] El-Amawy, A.; Latifi, S., Properties and performance of folded hypercubes, IEEE Transactions on Parallel and Distributed Systems, 2, 1, 31-42 (1991)
[2] Preparata, F. P.; Vuillemin, J., The cube-connected cycles, A versatile network for parallel computation, Communication of the ACM, 30-39 (May 1981)
[3] Youssef, A. S.; Narhari, B., The Banyan hypercube networks, IEEE Transactions on Parallel and Distributed Systems, 1, 2, 300-309 (1990)
[4] El-Amawy, A.; Latifi, S., Bridged hypercube networks, Journal of Parallel and Distributed Computing, 10, 90-95 (1991)
[5] Goodman, J. R.; Sequin, C. H., Hypertree: A multiprocessor interconnection topology, IEEE Transactions on Computers, C-30, 12, 923-933 (1981)
[6] Samatham, M. R.; Pradhan, D. K., The De Bruijn multiprocessor network: A versatile parallel processing and sorting network for VLSI, IEEE Transactions on Computers, 38, 4, 567-580 (1989) · Zbl 0671.94028
[7] Stone, H. S., Parallel processing with the perfect shuffle, IEEE Transactions on Computers, C-20, 2, 153-161 (1971) · Zbl 0214.42703
[8] Wu, C. L.; Feng, T., The universality of the shuffle exchange, IEEE Transactions on Computers, C-30, 5, 324-332 (1981) · Zbl 0463.94016
[9] Nanavati, A. A.; Iyengar, S. S., On optimal average message passing density in Moore graphs, Appl. Math. Lett., 7, 5, 67-70 (1994)
[10] Deo, N., Graph Theory with Applications to Engineering and Computer Science (1974), Prentice-Hall: Prentice-Hall New Jersey · Zbl 0285.05102
[11] Harary, F., Graph Theory, ((1972), Addison-Wesley), 22
[12] Chartrand, G.; Wilson, R. J., The Petersen graph, (Harary, F.; Maybee, J. S., Graphs and Applications, Proc. of the First Colorado Symposium on Graph Theory (1982), John Wiley & Sons: John Wiley & Sons New York), 69-100
[13] A.A. Nanavati and S.S. Iyengar, On optimal average message passing density in generalized Petersen graphs, Discrete Applied Mathematics; A.A. Nanavati and S.S. Iyengar, On optimal average message passing density in generalized Petersen graphs, Discrete Applied Mathematics
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.