Degree-Diameter Problem

A (Delta,D)-graph is a graph with maximum vertex degree Delta and diameter at most D. The order of a graph with degree Delta of diameter D is bounded by

 |G|<={(Delta(Delta-1)^D-2)/(Delta-2)   for Delta!=2; 2D+1   for Delta=2,

known as the Moore bound, is due to Moore circa 1958.

It is known that for Delta>=2 and D>=3, the Moore bound is attained only if Delta=2 and D=3, 7, and (possibly) 57 (Bermond et al. 1992).

It is therefore of interest to find graphs of a given diameter and maximum vertex degree that have vertex count as close as possible to the Moore bound (Sampels 1997).

See also

Moore Graph

Explore with Wolfram|Alpha


Bermond, J.-C. and Bollobás, B. "The Diameter of Graphs--A Survey." Congressus Numer. 3, 3-27, 1981.Bermond, J.-C.; Delorme, C.; and Quisquater, J J. "Table of Large (Delta,D)-Graphs." Disc. Appl. Math. 37/38, 575-577, 1992.Bozóki, S.; Szádoczki, Z.; and Tekile, H. A. "Filling in Pattern Designs for Incomplete Pairwise Comparison Matrices: (Quasi-)Regular Graphs with Minimal Diameter." 31 May 2020., M. "Large Networks with Small Diameter." In Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science. Berlin: Springer-Verlag, 1997.World Combinatorics Exchange. "The (Degree, Diameter) Problem for Graphs."

Referenced on Wolfram|Alpha

Degree-Diameter Problem

Cite this as:

Weisstein, Eric W. "Degree-Diameter Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications