Table of the largest known graphs of a given diameter and maximal degree

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Eloz002 (talk | contribs) at 10:30, 11 October 2008. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Table of the orders of the largest known graphs for the undirected Degree Diameter problem (July 2008):

d\k 2 3 4 5 6 7 8 9 10
3 10 20 38 70 132 196 336 600 1250
4 15 41 96 364 740 1 320 3 243 7 575 17 703
5 24 72 210 624 2 772 5 516 17 030 57 840 187 056
6 32 110 390 1404 7 917 19 383 76 461 307 845 1 253 615
7 50 168 672 2 756 11 988 52 768 249 660 1 223 050 6 007 230
8 57 253 1 100 5 060 39 672 131 137 734 820 4 243 100 24 897 161
9 74 585 1 550 8 200 75 893 279 616 1 686 600 12 123 288 65 866 350
10 91 650 2 286 13 140 134 690 583 083 4 293 452 27 997 191 201 038 922
11 104 715 3 200 19 500 156 864 1 001 268 7 442 328 72 933 102 600 380 000
12 133 786 4 680 29 470 359 772 1 999 500 15 924 326 158 158 875 1 506 252 500
13 162 851 6 560 40 260 531 440 3 322 080 29 927 790 249 155 760 3 077 200 700
14 183 916 8 200 57 837 816 294 6 200 460 55 913 932 600 123 780 7 041 746 081
15 186 1 215 11 712 76 518 1 417 248 8 599 986 90 001 236 1 171 998 164 10 012 349 898
16 198 1 600 14 640 132 496 1 771 560 14 882 658 140 559 416 2 025 125 476 12 951 451 931


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


Color Details
* The Petersen and Hoffman–Singleton graphs.
* Other non Moore but optimal graphs. More details are available.
* Graph found by James Allwright.
* Graph found by G. Wegner. Details about this graph are avaliable from other authors.
* Graphs found by Geoffrey Exoo.
* Family of graphs found by Brendan D. McKay, Mirka Miller and Jozef Širáň. More details are available in a paper by the authors.
* Graphs found by J. Gómez.
* Graph found by Mitjana M. and Francesc Comellas. This graph was also found independently by Michael Sampels.
* Graph found by Fiol, M.A. and Yebra, J.L.A.
* Graph found by Francesc Comellas and J. Gómez.
* Graphs found by G. Pineda-Villavicencio, J. Gómez, Mirka Miller and H. Pérez-Rosés. More details are available in a paper by the authors.
* Graphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň.
* Graphs found by Michael Sampels.
* Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors.
* A graph found by Marston Conder.


References

  • Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, MR0140437
  • Pineda-Villavicencioa, Guillermo; Gómez, José; Miller, Mirka; Pérez-Rosésd, Hebert (2006), "New Largest Graphs of Diameter 6", Electronic Notes in Discrete Mathematics, 24: 153–160

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree&oldid=244545646"