Result: A Backtracking Algorithm for Determining the Existence of Regular Graphs of Specified Girth and Excess

The study of cages focuses on finding (k, g)-graphs of minimal order. This dissertation generalizes the problem of finding cages to the determination of graphs with specified excess, thereby broadening the significance of the results. The (k, g, ε)-graph problem seeks to determine the existence or nonexistence of k-regular graphs with girth g and excess ε = n(G)−M(k, g) (where M(k, g) represents the Moore bound for cage graphs). Motivated by heuristic methods used to determine properties within the study of cages, we present a backtracking algorithm capable of constructing (k, g, ε)-graphs or determining their nonexistence. Chapter 2 provides our own formalization of well-established definitions and results within the study of cages. Additionally, we establish our own labeling convention to more precisely discuss (k, g, ε)-graph constructions. Historically, the study of cages has lacked a standard labeling convention, and the convention we introduce embeds graph data into vertex labels to improve algorithm efficiency by eliminating some computationally expensive calculations. Chapter 3 of this dissertation provides new information on necessary subgraphs of (k, g, ε)-graphs, if such graphs exist, and methods for determining that a given graph cannot be a subgraph of a (k, g, ε)-graph. The lemmas and theorems in this chapter identify safe edge additions for base graphs and forbidden substructures of (k, g, ε)-graphs. Building on Robertson’s argument that the order of the (4, 5)-cage could not be less than 19, we generalize related concepts for all odd girth (k, g, ε)-graphs and even girth (k, g, ε)-graphs assumed to be bipartite. Chapter 4 provides a backtracking algorithm to construct (k, g, ε)-graphs or determine their nonexistence for all ordered triplets (k, g, ε). Chapter 5 introduces improvements to the algorithm from Chapter 4 that enhance performance and reduce the search space. Enhancements which improve computational efficiency include forced neighbor detection, class-based pruning techniques, and array ...