Grahame: 1 revision imported

2019-01-03T14:39:32Z

1 revision imported

CW>JichengMa: /* Table of the orders of the largest known arc-transitive graphs for the undirected degree diameter problem */

2013-03-03T17:13:33Z

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

New page

==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 [http://en.wikipedia.org/wiki/Arc-transitive_graph 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 [http://en.wikipedia.org/wiki/Arc-transitive_graph arc-transitive graphs] in the undirected [[The Degree/Diameter Problem | degree diameter problem]] for arc-transitive graphs of [http://en.wikipedia.org/wiki/Degree_(graph_theory) degree] at most 3 ≤ ''d'' ≤ 20 and [http://en.wikipedia.org/wiki/Distance_(graph_theory) 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''.)

<center>
{| border="1"
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8''' || '''9''' || '''10'''
|-
| '''3'''
| align="center" |
{| border="2" style="background-color: red;"
| '''10'''
|-
| 3
|}
| align="center" |
{| border="2" style="background-color: red;"
| '''14'''
|-
| 4
|}
| align="center" |
{| border="2" style="background-color: red;"
| '''30'''
|-
| 5
|}
| align="center" |
{| border="2" style="background-color: red;"
| '''60'''
|-
| 2
|}
| align="center" |
{| border="2" style="background-color: red;"
| '''64'''
|-
| 2
|}
| align="center" |
{| border="2" style="background-color: red;"
| '''168'''
|-
| 1,2
|}
| align="center" |
{| border="2" style="background-color: red;"
| '''234'''
|-
| 5
|}
| align="center" |
{| border="2" style="background-color: red;"
| '''364'''
|-
| 2
|}
| align="center" |
{| border="2" style="background-color: red;"
| '''1250'''
|-
| 3
|}
|-
| '''4'''
| align="center" |
{| border="2" style="background-color: green;"
| 13
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: green;"
| 35
|-
| 3
|}
| align="center" |
{| border="2" style="background-color: green;"
| 81
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: blue;"
| 273
|-
| 2
|}
| align="center" |
{| border="2" style="background-color: blue;"
| 440
|-
| 4
|}
| align="center" |
{| border="2" style="background-color: green;"
| 720
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 2058
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: blue;"
| 1920
|-
| 2
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 4374
|-
| 1
|}
|-
| '''5'''
| align="center" |
{| border="2" style="background-color: green;"
| 16
|-
| 2
|}
| align="center" |
{| border="2" style="background-color: green;"
| 22
|-
| 2
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 96
|-
| 2
|}
| align="center" |
{| border="2" style="background-color: green;"
| 384
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 512
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 1500
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
|-
| '''6'''
| align="center" |
{| border="2" style="background-color: yellow;"
| 19
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 56
|-
| r
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 162
|-
| r
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 162
|-
| r
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 162
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
|-
| '''7'''
| align="center" |
{| border="2" style="background-color: yellow;"
| 14
|-
| r
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 78
|-
| r
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 384
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 464
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 406
|-
| 1
|}
| align="center" |
{| border="2" style="background-color: yellow;"
| 478
|-
| 1
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
|-
| '''8'''
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
|-
| '''9'''
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
|-
| '''10'''
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
| align="center" |
{| border="2" style="background:#ABCDEF;"
| Size
|-
| r
|}
|-
|}
</center>

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

<center>
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"
|'''Color''' || style="text-align: center;" |'''Details'''
|-
|style="background-color: red; text-align: center;" | * || Graphs found by [[Marston Conder]].
|-
|style="background-color: blue; text-align: center;" | * || Graphs found by Primoz Potocnik.
|-
|style="background-color: green; text-align: center;" | * || Graphs found by Jicheng Ma and Primoz Potocnik independently.
|-
|style="background-color: yellow; text-align: center;" | * || Graphs found by Jicheng Ma.
|-
|}
</center>

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

No study has been identified in this reserach area.

==References==

==External links==
* [http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt Marston Conder's data] listing the complete set of graphs found and their description.

[[Category:The Degree/Diameter Problem]]

← Older revision	Revision as of 14:39, 3 January 2019
(No difference)

The Degree Diameter Problem for Arc Transitive Graphs - Revision history

Grahame: 1 revision imported

CW>JichengMa: /* Table of the orders of the largest known arc-transitive graphs for the undirected degree diameter problem */