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

%I #31 May 16 2017 00:15:43

%S 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,

%T 10,16,50,62

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

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

%H Andries E. Brouwer, <a href="http://www.win.tue.nl/~aeb/graphs/cages/cages.html">Cages</a>

%H M. Daven and C. A. Rodger, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00342-2">(k,g)-cages are 3-connected</a>, Discr. Math., 199 (1999), 207-215.

%H Geoff Exoo, <a href="http://ginger.indstate.edu/ge/CAGES">Regular graphs of given degree and girth</a>

%H G. Exoo and R. Jajcay, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS16">Dynamic cage survey</a>, Electr. J. Combin. (2008, 2011).

%H Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890//remote/cages/">Cubic Cages</a>

%H Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/cages/allcages.html">Cages of higher valency</a>

%H Pak Ken Wong, <a href="https://dx.doi.org/10.1002/jgt.3190060103">Cages-a survey</a>, J. Graph Theory 6 (1982), no. 1, 1-22.

%F 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

%e First eight antidiagonals are:

%e 3 4 5 6 7 8 9 10

%e 4 6 10 14 24 30 58

%e 5 8 19 26 67 80

%e 6 10 30 42 ?

%e 7 12 40 62

%e 8 14 50

%e 9 16

%e 10

%Y Moore lower bound: A198300.

%Y 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).

%Y Graphs not required to be regular: A006787, A006856.

%K nonn,tabl,nice,hard,more

%O 0,1

%A _N. J. A. Sloane_, Apr 26 2000

%E Edited by _Jason Kimberley_, Apr 25 2010, Oct 26 2011, Dec 21 2012, Jan 01 2013