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).
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.