TOPICS
Search

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,
(1)

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

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. "Strategies for Interconnection Networks: Some Methods from Graph Theory." J. Parallel and Distributed Comput. 3, 433-449, 1986.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. 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

Subject classifications