This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000066 Smallest number of vertices in trivalent graph with girth (shortest cycle) = n. (Formerly M1013 N0380) 16
 4, 6, 10, 14, 24, 30, 58, 70, 112, 126 (list; graph; refs; listen; history; text; internal format)
 OFFSET 3,1 COMMENTS 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 REFERENCES 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). LINKS 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. FORMULA 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 CROSSREFS 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). Sequence in context: A276983 A061227 A274522 * A266730 A241160 A061645 Adjacent sequences:  A000063 A000064 A000065 * A000067 A000068 A000069 KEYWORD nonn,hard,more,nice AUTHOR EXTENSIONS 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. STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 17 18:58 EDT 2019. Contains 328127 sequences. (Running on oeis4.)