A054760 Table T(n,k) = order of (n,k)-cage (smallest n-regular graph of girth k), n >= 2, k >= 3, read by antidiagonals.

3, 4, 4, 5, 6, 5, 6, 8, 10, 6, 7, 10, 19, 14, 7, 8, 12, 30, 26, 24, 8, 9, 14, 40, 42, 67, 30, 9, 10, 16, 50, 62

Offset: 0

Author

N. J. A. Sloane, Apr 26 2000

Keywords

• nonn
• tabl
• nice
• hard
• more

Examples

			First eight antidiagonals are:
   3  4  5  6  7  8  9 10
   4  6 10 14 24 30 58
   5  8 19 26 67 80
   6 10 30 42  ?
   7 12 40 62
   8 14 50
   9 16
  10
		

References

• P. R. Christopher, Degree monotonicity of cages, Graph Theory Notes of New York, 38 (2000), 29-32.

Links

• Andries E. Brouwer, Cages
• M. Daven and C. A. Rodger, (k,g)-cages are 3-connected, Discr. Math., 199 (1999), 207-215.
• Geoff Exoo, Regular graphs of given degree and girth
• G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
• Gordon Royle, Cubic Cages
• Gordon Royle, Cages of higher valency
• Pak Ken Wong, Cages-a survey, J. Graph Theory 6 (1982), no. 1, 1-22.

Crossrefs

Moore lower bound: A198300.

Orders of cages: this sequence (n,k), A000066 (3,n), A037233 (4,n), A218553 (5,n), A218554 (6,n), A218555 (7,n), A191595 (n,5).

Graphs not required to be regular: A006787, A006856.

Formula

T(k,g) >= A198300(k,g) with equality if and only if: k = 2 and g >= 3; g = 3 and k >= 2; g = 4 and k >= 2; g = 5 and k = 2, 3, 7 or possibly 57; or g = 6, 8, or 12, and there exists a symmetric generalized g/2-gon of order k - 1. - Jason Kimberley, Jan 01 2013

Extensions

Edited by Jason Kimberley, Apr 25 2010, Oct 26 2011, Dec 21 2012, Jan 01 2013