Biregular Cages of Odd Girth

作者：Exoo Geoffrey^*; Jajcay Robert

来源：Journal of Graph Theory, 2016, 81(1): 50-56.

DOI：10.1002/jgt.21860

• cage
• biregular cage
• recursive construction
• girth

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 = 2t + 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.

• 出版日期2016-1