Abstract:
We consider the problem of construction of graphs with
given degree k and girth 5 and as few vertices as possible.
We give a construction of a family girth 5 graphs based on
relative difference sets. This family contains the smallest known
graph of degree 8 and girth 5 which was constructed by G. Royle,
four of the known cages including the HoffmanSingleton graph,
some graphs constructed by G. Exoo and some new smallest
known graphs.
This paper is published in
Discrete
Mathematics:
Leif K. Jørgensen, Girth 5 graphs from relative difference sets,
Discrete Mathematics 293 (2005) 177184.
G. Royle has a
web site
with a table of smallest known graphs with degree k and girth g.
Table below shows the smallest graph constructed in my paper for
7<=k<=16.
The graph with degree 7 is the HoffmanSingleton graph.
The graph with degree 8 was first constructed by
G. Royle.
The graphs with degree 10 and degree 13 were constructed by
G. Exoo
Degree

Order of graph

Reference

7

50

HoffmanSingleton

8

80

Royle

9

96


10

126

Exoo

11

156


12

216


13

240

Exoo

14

288


15

312


16

336


17

480


18

512


19

544


20

576

