|
%I M1013 N0380 #57 Jul 31 2017 09:51:18
%S 4,6,10,14,24,30,58,70,112,126
%N Smallest number of vertices in trivalent graph with girth (shortest cycle) = n.
%C Also called the order of the (3,n) cage graph.
%C Recently (unpublished) McKay and Myrvold proved that the minimal graph on 112 vertices is unique. - May 20 2003
%C If there are n vertices and e edges, then 3n=2e, so n is always even.
%C 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
%C 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
%D A. T. Balaban, Trivalent graphs of girth nine and eleven and relationships among cages, Rev. Roum. Math. Pures et Appl. 18 (1973) 1033-1043.
%D Brendan McKay, personal communication.
%D 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.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Gabriela Araujo-Pardo, Geoffrey Exoo, and Robert Jajcay, <a href="http://dx.doi.org/10.1016/j.disc.2015.10.009">Small bi-regular graphs of even girth</a> Discrete Mathematics 339.2 (2016): 658-667.
%H Andries E. Brouwer, <a href="http://www.win.tue.nl/~aeb/graphs/cages/cages.html">Cages</a>
%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 Brendan McKay, W. Myrvold and J. Nadon, <a href="http://users.cecs.anu.edu.au/~bdm/papers/cagereport.pdf">Fast backtracking principles applied to find new cages</a>, 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, 188-191.
%H M. O'Keefe and P. K. Wong, <a href="http://dx.doi.org/10.1016/0095-8956(80)90046-5">A smallest graph of girth 10 and valency 3</a>, J. Combin. Theory, B 29 (1980), 91-105.
%H Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/cages/">Cubic Cages</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CageGraph.html">Cage Graph</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 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
%Y Cf. A006787, A052453 (number of such graphs).
%Y 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).
%K nonn,hard,more,nice
%O 3,1
%A _N. J. A. Sloane_
%E Additional comments from _Matthew Cook_, May 15 2003
%E 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.
|
