Large graphs with small degree and diameter: A voltage assignment approach

Abstract

<p>The degree/diameter problem is to determine the largest order of a graph with given degree and diameter. Although many constructions have been considered in this area, a powerful one - the covering space construction -seems to have been overlooked. Paradoxically, many examples of graphs that are known as currently largest graphs for some degrees and diameters can be obtained by the covering space construction.</p> <p>The objective of the paper is to revisit the degree/diameter problem from this new perspective. The large covering graphs (called <i>lifts</i>) of small <i>base graphs</i> are described by means of the so-called <i>voltage assignments</i> on base graphs in finite groups. We do not try to find special graphs and special voltage assignments which would provide further record examples for given degree and diameter. Instead, we are interested in the potential of this method when applied to arbitrary graphs and groups. We derive a fairly general upper bound on the diameter of a lift in terms of the properties of the base voltage graph and discuss related questions.</p>