Families of Fixed Degree Graphs for Processor Interconnection

1 February 1984

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-33 (2) , 190-194
https://doi.org/10.1109/TC.1984.1676410

Abstract

A construction is presented which, given a fixed undirected graph of low degree and small average path length, yields an infinite sequence of low diameter graphs of increasing order and fixed degree. As examples of the construction, infinite sequences of low diameter graphs are presented with degrees in the range 3 to 30. Expressed as a function of the order of the graphs, the degree 3 sequence has diameter bounded above by 1.4722 log2 N + O(1), and the degree 4 sequence by 0.9083 log2N + O(1).

Keywords

This publication has 8 references indexed in Scilit:

GRAPHS AND INTERCONNECTION NETWORKS: DIAMETER AND VULNERABILITY
Published by Cambridge University Press (CUP) ,1983
The diameter of random regular graphs
Combinatorica, 1982
Dense Trivalent Graphs for Processor Interconnection
IEEE Transactions on Computers, 1982
High density graphs for processor interconnection
Information Processing Letters, 1981
On Moore graphs
Mathematical Proceedings of the Cambridge Philosophical Society, 1973
Improved Construction Techniques for (d, k) Graphs
IEEE Transactions on Computers, 1970
Minimal Regular Graphs of Girths Eight and Twelve
Canadian Journal of Mathematics, 1966
Topological constraints on interconnection-limited logic
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1964