

A054760


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


22



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


REFERENCES

P. R. Christopher, Degree monotonicity of cages, Graph Theory Notes of New York, 38 (2000), 2932.


LINKS

Table of n, a(n) for n=0..31.
Andries E. Brouwer, Cages
M. Daven and C. A. Rodger, (k,g)cages are 3connected, Discr. Math., 199 (1999), 207215.
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, Cagesa survey, J. Graph Theory 6 (1982), no. 1, 122.


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/2gon of order k  1.  Jason Kimberley, Jan 01 2013


EXAMPLE

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


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.
Sequence in context: A196379 A204002 A198300 * A079107 A205837 A262872
Adjacent sequences: A054757 A054758 A054759 * A054761 A054762 A054763


KEYWORD

nonn,tabl,nice,hard,more


AUTHOR

N. J. A. Sloane, Apr 26 2000


EXTENSIONS

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


STATUS

approved



