Table of The Orders of The Largest Known Graphs For The Undirected Degree Diameter Problem
Below is the table of the vertex numbers for the best-known graphs (as of October 2008) in the undirected degree diameter problem for graphs of degree at most 3 ≤ d ≤ 16 and diameter 2 ≤ k ≤ 10. Only a few of the graphs in this table (marked in bold) are known to be optimal (that is, largest possible). The remainder are merely the largest so far discovered, and thus finding a larger graph that is closer in order (in terms of the size of the vertex set) to the Moore bound is considered an open problem. Some general constructions are known for values of d and k outside the range shown in the table.
\ | 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. |
* | Optimal graphs which are not Moore graphs. |
* | Graph found by James Allwright. |
* | Graph found by G. Wegner. |
* | 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. |
* | Graph found by Marston Conder. |
Read more about this topic: Table Of The Largest Known Graphs Of A Given Diameter And Maximal Degree
Famous quotes containing the words table, orders, largest, degree and/or problem:
“In New York, pretending to be above the struggle means no seat on the bus and a table next to the kitchen.”
—Mason Cooley (b. 1927)
“There is nothing on earth more exquisite than a bonny book, with well-placed columns of rich black writing in beautiful borders, and illuminated pictures cunningly inset. But nowadays, instead of looking at books, people read them. A book might as well be one of those orders for bacon and bran.”
—George Bernard Shaw (18561950)
“Figure him there, with his scrofulous diseases, with his great greedy heart, and unspeakable chaos of thoughts; stalking mournful as a stranger in this Earth; eagerly devouring what spiritual thing he could come at: school-languages and other merely grammatical stuff, if there were nothing better! The largest soul that was in all England.”
—Thomas Carlyle (17951881)
“I began to realize that it was bigotry of the worst kind to say that its better to be dead than to be born retarded or blind or without a limb. Its a value judgment youre making about someones life, based on their degree of perfection.”
—Juli Loesch (b. c. 1953)
“How much atonement is enough? The bombing must be allowed as at least part-payment: those of our young people who are concerned about the moral problem posed by the Allied air offensive should at least consider the moral problem that would have been posed if the German civilian population had not suffered at all.”
—Clive James (b. 1939)