The Degree Diameter Problem for Arc Transitive Graphs

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 N^at(d,k) of vertices in an arc-transitive graph of maximum degree d and diameter k.

There are no better upper bounds for N^at(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 N^at(d,k), research activities in this problem follow the next two directions:

• Increasing the lower bounds for N^at(d,k) by constructing ever larger graphs.

• Lowering and/or setting upper bounds for N^at(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 N^at(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 N^at(d,k)

No study has been identified in this reserach area.

External links

• Marston Conder's data listing the complete set of graphs found and their description.