TOPICS

# Degree-Diameter Problem

A -graph is a graph with maximum vertex degree and diameter at most . The order of a graph with degree of diameter is bounded by

 (1)

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

It is known that for and , the Moore bound is attained only if and , 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).

Moore Graph

## Explore with Wolfram|Alpha

More things to try:

## References

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 -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. https://arxiv.org/abs/2006.01127.Sampels, 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." http://www-mat.upc.es/grup_de_grafs/table_g.html.

## Referenced on Wolfram|Alpha

Degree-Diameter Problem

## Cite this as:

Weisstein, Eric W. "Degree-Diameter Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Degree-DiameterProblem.html