×

zbMATH — the first resource for mathematics

New results for the degree/diameter problem. (English) Zbl 0806.05039
Summary: The results of computer searches for large graphs with given (small) degree and diameter are presented. The new graphs are Cayley graphs of semidirect products of cyclic groups and related groups. One fundamental use of our “dense graphs” is in the design of efficient communication network topologies.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
90B18 Communication networks in operations research
68R10 Graph theory (including graph drawing) in computer science
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv Link
References:
[1] Akers, IEEE Trans. Comput. 36 pp 885– (1987)
[2] Akers, IEEE Trans. Comput. 38 pp 555– (1989)
[3] Bar-Yehuda, Discr. Appl. Math. 37/38 pp 29– (1992)
[4] Algebraic Graph Theory. Cambridge University Press, Cambridge (1974). · Zbl 0797.05032
[5] Bannai, J. Fac. Sci. Univ. Tokyo 20 pp 191– (1973)
[6] Bannai, Discr. Math. 37 pp 147– (1981)
[7] Bermond, Info. Process. Lett. 15 pp 10– (1982)
[8] Bermond, J. Parallel Distrib. Comput. 3 pp 433– (1986)
[9] Bermond, Discr. Appl. Math. 37/38 pp 575– (1992)
[10] , and , Large Cayley graphs with small degree and diameter. Rapport de Recherche No. 392. LRI, Orsay (1987).
[11] and , Graph Theory with Applications. American Elsevier, New York (1976). · Zbl 1226.05083
[12] Campbell, IEEE Trans. Comput. 41 pp 218– (1992)
[13] Campbell, Discr. Appl. Math. 37/38 pp 65– (1992)
[14] and , CAYLEY. Quick Reference Guide. Sydney (October 1991).
[15] Carlsson, IEEE Trans. Comput. 34 pp 769– (1985)
[16] , and , Regular graphs with small diameter as models for interconnection networks. 3rd International Conference on Supercomputing, Boston, International Computing Institute (May 1988) 232–239.
[17] and , New large graphs with given degree and diameter. 7th International Conference on Graph Theory, Kalamazoo (June 1992).
[18] Damerell, Proc. Camb. Philos. Soc. 74 pp 227– (1973)
[19] Algebraic methods for efficient network constructions. Master’s Thesis, Department of Computer Science, University of Victoria, Victoria, BC, Canada (1991).
[20] Doty, IEEE Trans. Comput. C-33 pp 447– (1984)
[21] Topological constraints on interconnection-limited logic. Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logic Design (1964) 133–147.
[22] Erdõs, Networks 10 pp 87– (1980)
[23] Gómez, Discr. Math. 114 pp 219– (1993)
[24] Hoffman, IBM J. Res. Dev. 64 pp 15– (1960)
[25] Sabidussi, Monatsh. Math. 68 pp 426– (1969)
[26] Storwick, IEEE Trans. Comput. C-19 pp 1214– (1970)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.