The degree-diameter and cage problems : a study in structural graph theory

Abstract

The degree-diameter problem is stated as such: Find the largest connected graph of degree at most d and diameter k. The cage problem is similar: Find the smallest connected regular graph of degree d and girth g. These two problems have been of great interest for over forty years. Research in these problems has been undertaken in two main directions: constructing largest or smallest known graphs on one hand, and on the other, decreasing the theoretical upper bounds (in the degree-diameter problem) or increasing the theoretical lower bounds (in the cages problem). Constructing graphs of large order and small diameter, and small regular graphs of large girth, have many applications in present day technology and research. In the work presented in this thesis, we have successfully developed and improved ways of constructing such graphs. At present, most of the largest known graphs in the general and special classes cases, of degree d up to 20 and diameter k up to 10, were found as part of our effort. In the degree-diameter problem, making the distinction between different classes of graphs is very important. For example, the largest, or even optimal, bipartite or Cayley graphs are in many cases much smaller than the largest general graphs having the same values for d and k. Accordingly, we separate our findings to the general class, the bipartite class and the Cayley class. We also suggest that such clear distinctions could be adopted by other authors in future publications. Decreasing upper bounds for the degree-diameter problem is a very challenging task, and in general, the best known results have only decreased the theoretical upper bound, also known as the Moore bound, by at most 4, while the largest known graphs seem to diverge quickly from that bound. On the other hand, focusing on special classes of graphs, such as bipartite, Cayley or abelian voltage graphs, has allowed for significant improvements to be made. In this thesis we generalize the known results for the upper bound on the abelian lifts of dipoles, from the previously known upper bounds for diameters k = 2 and k = 3, to any given value of k.