Moore Graphs and Beyond: A survey of the Degree/Diameter Problem

TLDR

The degree/diameter problem seeks the largest graphs or digraphs with a given maximum degree and diameter, with Moore bounds providing tight upper limits only for special cases. This survey aims to tighten upper bounds and review constructions that approach the problem from below, offering a comprehensive overview of the current state of the degree/diameter problem. The authors focus on two research streams—improving upper bounds and constructing large graphs—and also examine related issues such as Moore‑like bounds for special graph classes and properties like connectivity, regularity, and surface embeddability. Additionally, the survey highlights results on various related problems.

Abstract

The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter.General upper bounds - called Moore bounds - for the order of such graphs and digraphs are attainable only for certain special graphs and digraphs. Finding better (tighter) upper bounds for the maximum possible number of vertices, given the other two parameters, and thus attacking the degree/diameter problem 'from above', remains a largely unexplored area. Constructions producing large graphs and digraphs of given degree and diameter represent a way of attacking the degree/diameter problem 'from below'.This survey aims to give an overview of the current state-of-the-art of the degree/diameter problem. We focus mainly on the above two streams of research. However, we could not resist mentioning also results on various related problems. These include considering Moore-like bounds for special types of graphs and digraphs, such as vertex-transitive, Cayley, planar, bipartite, and many others, on the one hand, and related properties such as connectivity, regularity, and surface embeddability, on the other hand.