Search: id:A000066
Results 1-1 of 1 results found.

%I A000066 M1013 N0380
%S A000066 4,6,10,14,24,30,58,70,112,126
%N A000066 Smallest number of vertices in trivalent graph with girth (shortest cycle) 
               = n.
%C A000066 Also called the (3,n) cage graph.
%C A000066 Recently (unpublished) McKay and Myrvold proved that the minimal graph 
               on 112 vertices is unique. - May 20 2003
%C A000066 If there are n vertices and e edges, then 3n=2e, so n is always even.
%D A000066 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000066 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000066 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 A000066 B. D. McKay, personal communication.
%D A000066 B. D. 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.
%D A000066 M. O'Keefe and P. K. Wong, A smallest graph of girth 10 and valency 3, 
               J. Combin. Theory, B 29 (1980), 91-105.
%D A000066 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 A000066 Wong, Pak Ken; Cages-a survey. J. Graph Theory 6 (1982), no. 1, 1-22.
%H A000066 Gordon Royle, <a href="http://www.cs.uwa.edu.au/~gordon/cages/">Cubic 
               Cages</a>
%H A000066 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               CageGraph.html">Link to a section of The World of Mathematics.</a>
%Y A000066 Cf. A054760, A006787, A052453 (number of such graphs).
%Y A000066 Sequence in context: A141247 A049632 A061227 this_sequence A061645 A084372 
               A140611
%Y A000066 Adjacent sequences: A000063 A000064 A000065 this_sequence A000067 A000068 
               A000069
%K A000066 nonn,hard,nice
%O A000066 3,1
%A A000066 N. J. A. Sloane (njas(AT)research.att.com).
%E A000066 Additional comments from Matthew Cook (matthewc(AT)caltech.edu), May 
               15, 2003
%E A000066 Balaban proved 112 as an upper bound for a(11). The proof that it is 
               also a lower bound is in the paper by B. D. McKay, W. Myrvold and 
               J. Nadon.

Search completed in 0.001 seconds