A regular graph with valency k and girth g will be referred to as a (/,. ~.,, ,:_';~,~,+ Petersen's graph is a (3, 5)-graph; indeed, it is the (unique) smallest (3. :,)-, ~,~;+ In general, the problem of finding a smallest (k, g)-graph is hard, an~ ~;-~,~: .~;;.-,~,' ~/~ is known only for a few values of k and g.
The particular case k =3, g=9 has been the subject of much e~ i~::~..t~r~,...,\ lower bound of 46 for the number of vertices can be obtainec: ';~ sir~:,plc arguments, and it is easy to show that, in fact, this bound c~tnnot be at~aiqed. With progressively more effort, it can be shown that 48, 50, and 52 vertices are hk,,'wise impossible. The alternative approach is to establish an upper bound by ac~!~:a!ly c~mstructing a (3,9)-graph. As long ago as 1952, R.M. Foster ke.:~'w ~,'f a (3, 9)-graph wiith 60 vertices: this graph was mentioned by Frucht [3] in 1955. and included in a list of symmetric trivalent graphs distributed by Foster at a co~aferenee held in 1966 at Waterloo, Canada. From about 1968 onwards many ttttempts have been made to improve on Poster's result. Balaban [1], Coxeter.. IEvat:s, Harries, Wynn, and Foster himself, have all made contributions. The sum, ~otal ~:f these efforts, up to November 1979. was the construction of ~o fewer t~7~an 19 mutually non-isomorphic (3, 9)-graphs with 611 vertices--but ulo smalle~ on~s. Little of this work has been published, since each attempt to prepare a paper has been overtaken by the discovery of a new graph or graphs. In fact. thr'ee retire (3, 9)-graphs with 60 vertices were found in the preliminary stages of ~',e preser0t investigation.
The main purpose of this note is to announce the existence of a ~3.9)-graph with 58 vertices. This graph is a significant, t, ut not necessarily final, co~llribution to the problem, since it is possible that smaller (3,9)-graphs exist.
The graph is displayed in Figs. i and 2, demgnstrating that it has at least two different Hamiltonian cycles. There are 80 9-cycles. The eigenvalues of the adjacency matrix are all distinct, and this means that an?/non-identity autcmorphism must be an involution [2, p. 103]. The automorphism group is a non-cyclic