Large Graphs with Given Degree and Diameter—Part I
- 1 September 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (9) , 857-860
- https://doi.org/10.1109/tc.1984.1676504
Abstract
The following problem arises in the study of interconnection networks: find graphs of given diameter and degree having the maximum number of vertices. In this correspondence we give some constructions of graphs proving in particular that lim△∞inf N(△, D).△-D ≥ 2-D, where N(△, D) is the maximum number of vertices of a graph with degree A and diameter D.Keywords
This publication has 10 references indexed in Scilit:
- Large bipartite graphs with given degree and diameterJournal of Graph Theory, 1985
- Line Digraph Iterations and the (d, k) Digraph ProblemIEEE Transactions on Computers, 1984
- Large graphs with given degree and diameter. IIJournal of Combinatorial Theory, Series B, 1984
- GRAPHS AND INTERCONNECTION NETWORKS: DIAMETER AND VULNERABILITYPublished by Cambridge University Press (CUP) ,1983
- Tables of large graphs wh given degree and diameterInformation Processing Letters, 1982
- Some New Results About the (d, k) Graph ProblemIEEE Transactions on Computers, 1982
- Dense Trivalent Graphs for Processor InterconnectionIEEE Transactions on Computers, 1982
- High density graphs for processor interconnectionInformation Processing Letters, 1981
- Design to Minimize Diameter on Building-Block NetworkIEEE Transactions on Computers, 1981
- Regular d-valent graphs of girth 6 and 2(d2−d+1) verticesJournal of Combinatorial Theory, 1970