The Degree Diameter Problem for Arc Transitive Graphs

From Combinatorics Wiki

Introduction

The degree/diameter problem for arc-transitive graphs can be stated as follows:

Given natural numbers d and k, find the largest possible number Nat(d,k) of vertices in an arc-transitive graph of maximum degree d and diameter k.

There are no better upper bounds for Nat(d,k) than the very general Moore bounds M(d,k)=d((d-1)k-2)(d-2)-1.

Therefore, in attempting to settle the values of Nat(d,k), research activities in this problem follow the next two directions:

  • Increasing the lower bounds for Nat(d,k) by constructing ever larger graphs.
  • Lowering and/or setting upper bounds for Nat(d,k) by proving the non-existence of arc-transitive graphs whose order is close to the Moore bounds M(d,k).

Increasing the lower bounds for Nat(d,k)

With the exception of the graphs obtained by Conder, no study has been identified in this reserach area.

Below is the unfinished table of the largest known arc-transitive graphs in the undirected degree diameter problem for arc-transitive graphs of degree at most 3 ≤ d ≤ 20 and diameter 2 ≤ k ≤ 10. Work in progress.

Table of the orders of the largest known arc-transitive graphs for the undirected degree diameter problem

Graphs in bold are known to be optimal. For each entry in the table we have the order of the graph and the largest value of r for which the known graph has r-arc-transitive automorphism group. (In some cases, where more than one graph exists, there can be two or more possibilities for this value of r.)

[math]d[/math]\[math]k[/math] 2 3 4 5 6 7 8 9 10
3
10
3
14
4
30
5
60
2
64
2
168
1,2
234
5
364
2
1250
3
4
13
1
35
3
81
1
273
2
440
4
720
1
2058
1
1920
2
4374
1
5
16
2
22
2
96
2
384
1
512
1
1500
r
Size
r
Size
r
Size
r
6
19
1
56
r
162
r
162
r
162
r
Size
r
Size
r
Size
r
Size
r
7
14
r
78
r
384
1
464
1
406
1
478
1
Size
r
Size
r
Size
r
8
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
9
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
10
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r
Size
r

The following table is the key to the colors in the table presented above:

Color Details
* Graphs found by Marston Conder.
* Graphs found by Primoz Potocnik.
* Graphs found by Jicheng Ma and Primoz Potocnik independently.
* Graphs found by Jicheng Ma.

Lowering and/or setting upper bounds for Nat(d,k)

No study has been identified in this reserach area.

References

External links