Biregular Cages of Odd Girth. Issue 1 (12th March 2015) - Exoo, Geoffrey; Jajcay, Robert
Abstact: Biregular ( { r, m } ; g ) ‐cages are graphs of girth g that contain vertices of degrees r and m and are of the smallest order among all such graphs. We show that for every r ≥ 3 and every odd g = 2 t + 1 ≥ 3, there exists an integer m 0 such that for every even m ≥ m 0, the biregular ( { r, m }, g ) ‐cage is of order equal to a natural lower bound analogous to the well‐known Moore bound. In addition, when r is odd, the restriction on the parity of m can be removed, and there exists an integer m 0 such that a biregular ( { r, m }, g ) ‐cage of order equal to this lower bound exists for all m ≥ m 0 . This is in stark contrast to the result classifying all cages of degree k and girth g whose order is equal to the Moore bound.