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.

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

njas

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.