Computer Aided Constructions of Cages (Logic, Algebraic system, Language and Related Areas in Computer Science)

Abstract

A k-regular graph of girth g and minimal order is called a (k, g)-cage. The orders of cages are determined for only few sets of parameter pairs (k, g), and the general problem of determining these orders and constructing at least one (k, g)-cage for each pair of parameters is called the Cage Problem. The voltage lift construction is among the most widely used constructions of small (k, g)-graphs, with the orders of the constructed graphs depending on the choice of a base graph, a voltage group, and a specific voltage assignment. Successful application of the voltage lift construction therefore often requires significant computer aided experimentation with the three fundamental ingredients. We survey some known results concerning the voltage lift construction, and discuss ways to decrease the orders of the smallest known (k, g)-graphs for some specific parameter pairs (k, g).