A survey of the degree/diameter problem for undirected graphs
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
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.
Description
Keywords
Algebraic graph theory, Degree/diameter problem, Graph theory, Moore graphs