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 Hoffman-Singleton 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) 177-184.
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 Hoffman-Singleton 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
|
Hoffman-Singleton
|
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
|
|