A218554 -id:A218554 - cp's OEIS frontend

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

N. J. A. Sloane, Apr 26 2000

			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

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

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.

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.

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

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

A000066 Smallest number of vertices in trivalent graph with girth (shortest cycle) = n.

Original entry on oeis.org

4, 6, 10, 14, 24, 30, 58, 70, 112, 126

Offset: 3

N. J. A. Sloane

Also called the order of the (3,n) cage graph.
Recently (unpublished) McKay and Myrvold proved that the minimal graph on 112 vertices is unique. - May 20 2003
If there are n vertices and e edges, then 3n=2e, so n is always even.
Current lower bounds for a(13)..a(32) are 202, 258, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072. - from Table 3 of the Dynamic cage survey via Jason Kimberley, Dec 31 2012
Current upper bounds for a(13)..a(32) are 272, 384, 620, 960, 2176, 2560, 4324, 5376, 16028, 16206, 49326, 49608, 108906, 109200, 285852, 415104, 1141484, 1143408, 3649794, 3650304. - from Table 3 of the Dynamic cage survey via Jason Kimberley, Dec 31 2012

A. T. Balaban, Trivalent graphs of girth nine and eleven and relationships among cages, Rev. Roum. Math. Pures et Appl. 18 (1973) 1033-1043.
Brendan McKay, personal communication.
H. Sachs, On regular graphs with given girth, pp. 91-97 of M. Fiedler, editor, Theory of Graphs and Its Applications: Proceedings of the Symposium, Smolenice, Czechoslovakia, 1963. Academic Press, NY, 1964.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Gabriela Araujo-Pardo, Geoffrey Exoo, and Robert Jajcay, Small bi-regular graphs of even girth Discrete Mathematics 339.2 (2016): 658-667.
Andries E. Brouwer, Cages
Geoff Exoo, Regular graphs of given degree and girth
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
Brendan McKay, W. Myrvold and J. Nadon, Fast backtracking principles applied to find new cages, 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, 188-191.
M. O'Keefe and P. K. Wong, A smallest graph of girth 10 and valency 3, J. Combin. Theory, B 29 (1980), 91-105.
Gordon Royle, Cubic Cages
Eric Weisstein's World of Mathematics, Cage Graph
Pak Ken Wong, Cages-a survey, J. Graph Theory 6 (1982), no. 1, 1-22.

Cf. A006787, A052453 (number of such graphs).

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

For all g > 2, a(g) >= A027383(g-1), with equality if and only if g = 3, 4, 5, 6, 8, or 12. - Jason Kimberley, Dec 21 2012 and Jan 01 2013

Additional comments from Matthew Cook, May 15 2003

Balaban proved 112 as an upper bound for a(11). The proof that it is also a lower bound is in the paper by Brendan McKay, W. Myrvold and J. Nadon.

A198306 Moore lower bound on the order of a (6,g)-cage.

Original entry on oeis.org

7, 12, 37, 62, 187, 312, 937, 1562, 4687, 7812, 23437, 39062, 117187, 195312, 585937, 976562, 2929687, 4882812, 14648437, 24414062, 73242187, 122070312, 366210937, 610351562, 1831054687, 3051757812, 9155273437, 15258789062

Offset: 3

Jason Kimberley, Oct 30 2011

Gordon Royle, Cages of higher valency
Index entries for linear recurrences with constant coefficients, signature (1,5,-5).

Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), this sequence (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7).

LinearRecurrence[{1,5,-5},{7,12,37},30] (* Harvey P. Dale, Jun 28 2015 *)

a(2*i) = 2*Sum_{j=0..i-1} 5^j = string "2"^i read in base 5.
a(2*i+1) = 5^i + 2*Sum_{j=0..i-1} 5^j = string "1"*"2"^i read in base 5.
a(n) <= A218554(n). - Jason Kimberley, Dec 21 2012
a(n) = a(n-1)+5*a(n-2)-5*a(n-3). G.f.: -x^3*(10*x^2-5*x-7) / ((x-1)*(5*x^2-1)). - Colin Barker, Feb 01 2013
From Colin Barker, Nov 25 2016: (Start)
a(n) = (5^(n/2) - 1)/2 for n>2 and even.
a(n) = (3*5^((n-1)/2) - 1)/2 for n>2 and odd. (End)
E.g.f.: (5*cosh(sqrt(5)*x) - 5*cosh(x) - 5*sinh(x) + 3*sqrt(5)*sinh(sqrt(5)*x) - 10*x*(1 + x))/10. - Stefano Spezia, Apr 07 2022

A037233 Order of (4,n) cage, i.e., minimal order of 4-regular graph of girth n.

Original entry on oeis.org

5, 8, 19, 26, 67, 80

Offset: 3

Erich Friedman

a(9) <= 275, a(10) <= 384, a(12) = 728. - From Royle's page via Jason Kimberley, Dec 26 2012

Andries E. Brouwer, Cages
Geoff Exoo, Regular graphs of given degree and girth
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
Gordon Royle, Cages of higher valency
Eric Weisstein's World of Mathematics, Cage Graph (claims too much)

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

a(n) >= A062318(n+1). - Jason Kimberley, Dec 21 2012

Extended by Jason Kimberley, Apr 25 2010

A191595 Order of smallest n-regular graph of girth 5.

Original entry on oeis.org

5, 10, 19, 30, 40, 50

Offset: 2

N. J. A. Sloane, Jun 07 2011

Current upper bounds for a(8)..a(20) are 80, 96, 124, 154, 203, 230, 288, 312, 336, 448, 480, 512, 576. - Corrected from "Lower" to "Upper" and updated, from Table 4 of the Dynamic cage survey, by Jason Kimberley, Dec 29 2012

Current lower bounds for a(8)..a(20) are 67, 86, 103, 124, 147, 174, 199, 230, 259, 294, 327, 364, 403. - from Table 4 of the Dynamic cage survey via Jason Kimberley, Dec 31 2012

M. Abreu et al., A family of regular graphs of girth 5, Discrete Math., 308 (2008), 1810-1815.
Andries E. Brouwer, Cages
Geoff Exoo, Regular graphs of given degree and girth
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
G. Royle, Cages of higher valency

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

Moore lower bound on the orders of (k,g) cages: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), A198306(k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10),A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Nov 02 2011

a(n) >= A002522(n) with equality if and only if n = 2, 3, 7 or possibly 57. - Jason Kimberley, Nov 02 2011

a(2) = 5 prepended by Jason Kimberley, Jan 02 2013

A218553 Order of (5,n) cage, i.e., minimal order of 5-regular graph of girth n.

Original entry on oeis.org

6, 10, 30, 42

Offset: 3

Arkadiusz Wesolowski, Nov 02 2012

a(7) <= 152, a(8) = 170, a(12) = 2730. - From Royle's page via Jason Kimberley, Dec 21 2012

Andries E. Brouwer, Cages
Geoff Exoo, Regular graphs of given degree and girth
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
Gordon Royle, Cages of higher valency
Eric Weisstein's World of Mathematics, Cage Graph (claims too much)

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

a(n) >= A061547(n+1).

a(7) deleted by Jason Kimberley, Dec 21 2012

A218555 Order of (7,n) cage, i.e., minimal order of 7-regular graph of girth n.

Original entry on oeis.org

8, 14, 50, 90

Offset: 3

Arkadiusz Wesolowski, Nov 02 2012

a(8) <= 658, a(12) <= 32928. - Jason Kimberley, Dec 29 2012

Andries E. Brouwer, Cages
G. Exoo, Regular graphs of given degree and girth
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
Gordon Royle, Cages of higher valency
Eric Weisstein's World of Mathematics, Cage Graph (claims too much)

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

a(n) >= A198307(n).

Edited by Jason Kimberley, Dec 21 2012

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A000066 Smallest number of vertices in trivalent graph with girth (shortest cycle) = n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A198306 Moore lower bound on the order of a (6,g)-cage.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A037233 Order of (4,n) cage, i.e., minimal order of 4-regular graph of girth n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A191595 Order of smallest n-regular graph of girth 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A218553 Order of (5,n) cage, i.e., minimal order of 5-regular graph of girth n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A218555 Order of (7,n) cage, i.e., minimal order of 7-regular graph of girth n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions