3,1

Also called 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.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

A. T. Balaban, Trivalent graphs of girth nine and eleven and relationships among cages, Rev. Roum. Math. Pures et Appl. 18 (1973) 1033-1043.

B. D. McKay, personal communication.

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.

M. O'Keefe and P. K. Wong, A smallest graph of girth 10 and valency 3, J. Combin. Theory, B 29 (1980), 91-105.

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.

Wong, Pak Ken; Cages-a survey. J. Graph Theory 6 (1982), no. 1, 1-22.

Gordon Royle, Cubic Cages

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

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

Sequence in context: A141247 A049632 A061227 this_sequence A061645 A084372 A140611

Adjacent sequences: A000063 A000064 A000065 this_sequence A000067 A000068 A000069

nonn,hard,nice

N. J. A. Sloane (njas(AT)research.att.com).

Additional comments from Matthew Cook (matthewc(AT)caltech.edu), 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 B. D. McKay, W. Myrvold and J. Nadon.