http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Arc_Transitive_Graphs&feed=atom&action=history
The Degree Diameter Problem for Arc Transitive Graphs - Revision history
2024-03-29T10:05:24Z
Revision history for this page on the wiki
MediaWiki 1.31.1
http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Arc_Transitive_Graphs&diff=295&oldid=prev
Grahame: 1 revision imported
2019-01-03T14:39:32Z
<p>1 revision imported</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr class="diff-title" lang="en-GB">
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">Revision as of 14:39, 3 January 2019</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en-GB"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>
Grahame
http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Arc_Transitive_Graphs&diff=294&oldid=prev
CW>JichengMa: /* Table of the orders of the largest known arc-transitive graphs for the undirected degree diameter problem */
2013-03-03T17:13:33Z
<p><span dir="auto"><span class="autocomment">Table of the orders of the largest known arc-transitive graphs for the undirected degree diameter problem</span></span></p>
<p><b>New page</b></p><div>==Introduction==<br />
<br />
The '''degree/diameter problem for arc-transitive graphs''' can be stated as follows:<br />
<br />
''Given natural numbers ''d'' and ''k'', find the largest possible number ''N<sup>at</sup>(d,k)'' of vertices in an [http://en.wikipedia.org/wiki/Arc-transitive_graph arc-transitive graph] of maximum degree ''d'' and diameter ''k''.''<br />
<br />
There are no better upper bounds for ''N<sup>at</sup>(d,k)'' than the very general ''Moore bounds'' ''M(d,k)=d((d-1)<sup>k</sup>-2)(d-2)<sup>-1</sup>''. <br />
<br />
Therefore, in attempting to settle the values of ''N<sup>at</sup>(d,k)'', research activities in this problem follow the next two directions:<br />
<br />
* Increasing the lower bounds for ''N<sup>at</sup>(d,k)'' by constructing ever larger graphs.<br />
<br />
* Lowering and/or setting upper bounds for ''N<sup>at</sup>(d,k)'' by proving the non-existence of arc-transitive graphs whose order is close to the Moore bounds ''M(d,k)''.<br />
<br />
==Increasing the lower bounds for N<sup>at</sup>(d,k)==<br />
<br />
With the exception of the graphs obtained by Conder, no study has been identified in this reserach area.<br />
<br />
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&nbsp;≤&nbsp;''d''&nbsp;≤&nbsp;20 and [http://en.wikipedia.org/wiki/Distance_(graph_theory) diameter] 2&nbsp;≤&nbsp;''k''&nbsp;≤&nbsp;10. '''Work in progress.'''<br />
<br />
===Table of the orders of the largest known arc-transitive graphs for the undirected degree diameter problem===<br />
<br />
Graphs in bold are known to be optimal. For each entry in the table we have the order of the graph and the largest <br />
value of ''r'' for which the known graph has ''r''-arc-transitive automorphism group. (In some cases, where more <br />
than one graph exists, there can be two or more possibilities for this value of ''r''.) <br />
<br />
<center> <br />
{| border="1"<br />
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8''' || '''9''' || '''10''' <br />
|-<br />
| '''3'''<br />
| align="center" |<br />
{| border="2" style="background-color: red;" <br />
| '''10'''<br />
|-<br />
| 3<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: red;"<br />
| '''14'''<br />
|-<br />
| 4<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: red;"<br />
| '''30'''<br />
|-<br />
| 5<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: red;" <br />
| '''60'''<br />
|-<br />
| 2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: red;" <br />
| '''64'''<br />
|-<br />
| 2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: red;" <br />
| '''168'''<br />
|-<br />
| 1,2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: red;" <br />
| '''234'''<br />
|-<br />
| 5<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: red;"<br />
| '''364'''<br />
|-<br />
| 2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: red;" <br />
| '''1250'''<br />
|-<br />
| 3<br />
|}<br />
|-<br />
| '''4'''<br />
| align="center" |<br />
{| border="2" style="background-color: green;" <br />
| 13<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: green;" <br />
| 35<br />
|-<br />
| 3<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: green;" <br />
| 81<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: blue;" <br />
| 273<br />
|-<br />
| 2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: blue;" <br />
| 440<br />
|-<br />
| 4<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: green;" <br />
| 720<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 2058<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: blue;" <br />
| 1920<br />
|-<br />
| 2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 4374<br />
|-<br />
| 1<br />
|}<br />
|-<br />
| '''5'''<br />
| align="center" |<br />
{| border="2" style="background-color: green;" <br />
| 16<br />
|-<br />
| 2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: green;" <br />
| 22<br />
|-<br />
| 2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 96<br />
|-<br />
| 2<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: green;" <br />
| 384<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 512<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 1500<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
|-<br />
| '''6'''<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 19<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 56<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 162<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 162<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 162<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
|-<br />
| '''7'''<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 14<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 78<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 384<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 464<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 406<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background-color: yellow;" <br />
| 478<br />
|-<br />
| 1<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
|-<br />
| '''8'''<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
|-<br />
| '''9'''<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
|-<br />
| '''10'''<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:#ABCDEF;" <br />
| Size<br />
|-<br />
| r<br />
|}<br />
|-<br />
|}<br />
</center><br />
<br />
The following table is the key to the colors in the table presented above:<br />
<br />
<center><br />
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"<br />
|'''Color''' || style="text-align: center;" |'''Details'''<br />
|-<br />
|style="background-color: red; text-align: center;" | * || Graphs found by [[Marston Conder]].<br />
|-<br />
|style="background-color: blue; text-align: center;" | * || Graphs found by Primoz Potocnik. <br />
|-<br />
|style="background-color: green; text-align: center;" | * || Graphs found by Jicheng Ma and Primoz Potocnik independently.<br />
|-<br />
|style="background-color: yellow; text-align: center;" | * || Graphs found by Jicheng Ma. <br />
|-<br />
|}<br />
</center><br />
<br />
==Lowering and/or setting upper bounds for N<sup>at</sup>(d,k)==<br />
<br />
No study has been identified in this reserach area.<br />
<br />
==References==<br />
<br />
<br />
==External links==<br />
* [http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt Marston Conder's data] listing the complete set of graphs found and their description.<br />
<br />
<br />
<br />
<br />
[[Category:The Degree/Diameter Problem]]</div>
CW>JichengMa