Tabulka největších známých grafů daného průměru a maximálního stupně - Table of the largest known graphs of a given diameter and maximal degree - Wikipedia

v teorie grafů, problém s průměrem stupně je problém najít co největší graf pro dané maximum stupeň a průměr. The Moore vázán stanoví limity, ale po mnoho let se matematici v oboru zajímali o přesnější odpověď. Níže uvedená tabulka uvádí aktuální pokrok v tomto problému (s výjimkou případu stupně 2, kde jsou největší grafy cykly s lichým počtem vrcholů).

Tabulka objednávek největších známých grafů pro problém s neorientovaným průměrem stupňů

Níže je tabulka čísel vrcholů nejznámějších grafů (k říjnu 2008) v neorientovaných problém s průměrem stupně pro grafy stupně nejvýše 3 ≤d ≤ 16 a průměr 2 ≤k ≤ 10. O několika málo grafech v této tabulce (označených tučně) je známo, že jsou optimální (tj. Největší možné). Zbytek jsou pouze největší dosud objevené, a proto je hledání většího grafu, který je blíže v pořadí (z hlediska velikosti sady vrcholů) k Mooreově vazbě, považován za otevřený problém. Některé obecné konstrukce jsou známé pro hodnoty d a k mimo rozsah uvedený v tabulce.

k
d
2345678910
3102038701321963606001250
41541983647401 3203 2437 57517 703
524722126242 7725 51617 03057 840187 056
63211139014047 91719 38376 461331 3871 253 615
7501686722 75611 98852 768249 6601 223 0506 007 230
8572531 1005 06039 672131 137734 8204 243 10024 897 161
9745851 5508 26875 893279 6161 697 68812 123 28865 866 350
10916502 28613 140134 690583 0834 293 45227 997 191201 038 922
111047153 20019 500156 8641 001 2687 442 32872 933 102600 380 000
121337864 68029 470359 7721 999 50015 924 326158 158 8751 506 252 500
131628516 56040 260531 4403 322 08029 927 790249 155 7603 077 200 700
141839168 20057 837816 2946 200 46055 913 932600 123 7807 041 746 081
151871 21511 71276 5181 417 2488 599 98690 001 2361 171 998 16410 012 349 898
162001 60014 640132 4961 771 56014 882 658140 559 4162 025 125 47612 951 451 931

Následující tabulka je klíčem k barvám v tabulce uvedené výše:

BarvaDetaily
*The Petersen a Hoffman – Singleton grafy.
*Optimální grafy, které nejsou Mooreovy grafy.
*Graf nalezen Jamesem Allwrightem.
*Graf nalezen G. Wegnerem.
*Grafy nalezené Geoffreyem Exoo.
*McKay – Miller – Širáň grafy našel McKay, Miller & Širáň (1998)
*Grafy nalezené J. Gómezem.
*Graf nalezli Mitjana M. a Francesc Comellas. Tento graf také nezávisle našel Michael Sampels.
*Graf nalezen Fiol, M.A. a Yebra, J.L.A.
*Graf nalezen Francescem Comellasem a J. Gómezem.
*Grafy nalezené G. Pinedou-Villavicencio, J. Gómezem, Mirka Miller a H. Pérez-Rosés. Další podrobnosti jsou k dispozici v příspěvku autorů.
*Grafy nalezené Eyalem Lozem. Další podrobnosti jsou k dispozici v příspěvku Eyal Loz a Jozef Širáň.
*Grafy nalezené Michaelem Sampelsem.
*Grafy nalezli Michael J. Dinneen a Paul Hafner. Další podrobnosti jsou k dispozici v příspěvku autorů.
*Graf nalezen Marston Conder.

Reference

  • Hoffman, Alan J .; Singleton, Robert R. (1960), „Mooreovy grafy o průměru 2 a 3“ (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147 / kolo 45.0497, PAN  0140437

externí odkazy