A survey of the degree/diameter problem for undirected graphs

Abstract

Given a fixed diameter and maximum degree, the degree/diameter problem involves finding the maximum possible order of a graph. The Moore bound represents the upper threshold that such an order may achieve, and only few graphs reach this threshold. In this thesis, we explore these graphs, including the elusive, hypothetical Moore graph of degree 57. This thesis will also examine graphs that fail to achieve equality in the Moore bound by only a few vertices. These graphs also turn out to be scarce. Finally, we look at a related problem, the Moore bipartite bound, and examine graphs that come very close to achieving this upper bound.