Biregular Cages of Odd Girth. Issue 1 (12th March 2015)

• Record Type: Journal Article
• Authors: Exoo, Geoffrey; Jajcay, Robert
• Is Part Of: Journal of graph theory. Volume 81:Issue 1(2016)
• Page Start: 50
• Page End: 56
• Publication Date: 2015-03-12
• Subjects: cage -- biregular cage -- recursive construction -- girth; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21860
• Languages: English
• ISSNs: 0364-9024

Abstract

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.