与えられた直径と最大次数を持つ既知の最大グラフの表

グラフ理論において、次数直径問題とは、与えられた最大次数と直径に対して、可能な限り最大のグラフを見つける問題です。ムーアの限界によってこの問題には限界が設けられていますが、この分野の数学者は長年にわたり、より正確な答えを求めてきました。以下の表は、この問題の現在の進捗状況を示しています（次数2の場合、最大のグラフは奇数個の頂点を持つ 閉路となります）。

無向次数直径問題における既知の最大グラフの位数表

以下は、次数が最大 3 ≤  d  ≤ 16、直径が 2 ≤  k ≤ 10 のグラフに対する無向次数直径問題における最もよく知られているグラフ（2024年6月時点）の頂点番号の表です 。この表のグラフのうち、最適（つまり、可能な限り最大）であることが知られているのはごくわずかです（太字で示されています）。残りのグラフは、これまでに発見された最大のグラフに過ぎません。したがって、頂点集合のサイズの観点からムーア限界に近い、より大きなグラフを見つけることは未解決問題と考えられています。表に示されている範囲外 のdおよびkの値に対しても、いくつかの一般的な構成が知られています。

け
d
2345678910
3 10 [ g 1 ]20 [ g 2 ]38 [ g 3 ]70 [ g 4 ]132 [ g 5 ]196 [ g 5 ]360 [ g 6 ]600 [ g 5 ]1250 [ g 7 ]
4 15 [ g 2 ]41 [ g 8 ]98 [ g 5 ]364 [ g 9 ]740 [ g 10 ]1 3203 2437 57517 703
5 24 [ g 2 ]72 [ g 5 ]212 [ g 5 ]6242 772 [ g 11 ]5 5161703057,840187 056
6 32 [ g 12 ]111 [ g 5 ]39014047 917 [ g 11 ]19 38376 891 [ g 13 ]331 387 [ g 14 ]1 253 615
7 50 [ g 15 ]168 [ g 5 ]672 [ g 16 ]2 756 [ g 17 ]12 264 [ g 13 ]53 020 [ g 13 ]249 6601 223 0506 007 230
8 57 [ g 18 ]253 [ g 19 ]1 1005 115 [ g 13 ]39 672 [ g 20 ]131 137734 8204 243 10024 897 161
9 74 [ g 18 ]585 [ g 9 ]1 640 [ g 13 ]8 268 [ g 14 ]75 893 [ g 11 ]279 6161 697 688 [ g 14 ]12 123 28865 866 350
10 91 [ g 18 ]650 [ g 9 ]2 331 [ g 13 ]13 203 [ g 13 ]134 690 [ g 20 ]583 0834 293 45227 997 191201 038 922
11 104 [ g 5 ]715 [ g 9 ]3 200 [ g 21 ]19 620 [ g 13 ]156 864 [ g 21 ]1 001 2687 442 32872 933 102600 380 000
12 133 [ g 22 ]786 [ g 20 ]4 680 [ g 23 ]29 621 [ g 13 ]359 772 [ g 11 ]1 999 50015,924,326158 158 8751 506 252 500
13 162 [ g 24 ]856 [ g 25 ]6 560 [ g 21 ]40 488 [ g 13 ]531 440 [ g 21 ]3 322 08029,927,790249 155 7603 077 200 700
14 183 [ g 22 ]916 [ g 20 ]8 200 [ g 21 ]58 095 [ g 13 ]816 294 [ g 11 ]6 200 460 [ g 26 ]55 913 932600 123 7807 041 746 081
15 187 [ g 27 ]1 215 [ g 28 ]11 712 [ g 21 ]77 520 [ g 13 ]1 417 248 [ g 21 ]8 599 98690 001 2361 171 998 16410 012 349 898
16 200 [ g 29 ]1 600 [ g 28 ]14 640 [ g 21 ]132 496 [ g 28 ]1 771 560 [ g 21 ]14 882 658 [ g 26 ]140 559 4162 025 125 47612 951 451 931

脚注のない項目は、Loz & Širáň (2008)によって発見されました。それ以外の場合、表の脚注は、与えられた頂点数を達成するグラフの起源を示しています。

  1. ^ピーターセングラフ。
  2. ^ a b c最適グラフはElspas (1964)によって最適であることが証明されました。
  3. ^最適グラフはDoty（1982）によって発見され、 Buset（2000）によって最適であることが証明されました。
  4. ^ Alegre、Fiol、Yebra（1986）によって発見されたグラフ。
  5. ^ a b c d e f g h i 1998年から2010年にかけてGeoffrey Exooが発見したグラフ。
  6. ^ 2018年にJianxiang Chenが発見したグラフ。
  7. ^ Conder (2006)が発見したグラフ。
  8. ^ Allwright (1992)が発見したグラフ。
  9. ^ a b c d Delorme (1985a)によって発見されたグラフ。
  10. ^グラフはComellas & Gómez (1994)によって発見されました。
  11. ^ a b c d e Pineda-Villavicencioらによって発見されたグラフ。 (2006)。
  12. ^最適グラフはWegner (1977)によって発見され、 Molodtsov (2006)によって最適であることが証明されました。
  13. ^ a b c d e f g h i j k l Comellas (2024)によって発見されたグラフ。
  14. ^ a b c Canale & Rodríguez (2012)が発見したグラフ。
  15. ^ホフマン–シングルトングラフ。
  16. ^このグラフはSampels (1997)によって発見されました。
  17. ^ Dinneen & Hafner (1994)によって発見されたグラフ。
  18. ^ a b c Storwick (1970)によって発見されたグラフ。
  19. ^グラフは 1995 年に Margarida Mitjana と Francesc Comellas によって発見され、 Sampels (1997 年)によって独立して発見されました。
  20. ^ a b c d Gómez (2009)が発見したグラフ。
  21. ^ a b c d e f g h i Gómez & Fiol (1985)によって発見されたグラフ。
  22. ^ a b Delorme & Farhi (1984)によって発見されたグラフ。
  23. ^このグラフはBermond、Delorme、Farhi (1982)によって発見されました。
  24. ^マッケイ、ミラー、シランのグラフはMcKay、Miller、シラン (1998)によって発見されました。
  25. ^ 2021年にVlad Pelakhaty氏が発見したグラフ。
  26. ^ a b Gómez、Fiol、Serra（1993）によって発見されたグラフ。
  27. ^このグラフは 2012 年に Eduardo A. Canale 氏によって発見されました。
  28. ^ a b c Delorme (1985b)によって発見されたグラフ。
  29. ^ Abas (2016)が発見したグラフ。

参考文献

  • コメラス、フランセスク。ホセ・ゴメス (1994)。 「指定された次数と直径を持つ新しい大きなグラフ」。arXiv : math/9411218。
  • Comellas, Francesc (2024). 「与えられた次数と直径を持つ大きなグラフの表」. arXiv : 2406.18994 [ math.CO ].
  • Doty, Karl (1982)、「大規模正規相互接続ネットワーク」、第3回国際分散コンピューティングシステム会議論文集、IEEEコンピュータ協会、pp.  312– 317
  • エルスパス、バーナード（1964）、「相互接続制限論理における位相的制約」、1964年スイッチング回路理論および論理設計に関する第5回年次シンポジウム議事録、pp.  133– 137、doi：10.1109/SWCT.1964.27
  • ゴメス、ホセ（2009）「いくつかの新しい大きな（Δ, 3）グラフ」、ネットワーク、53（1）：1– 5、doi：10.1002 / NET.V53：1
  • ゴメス、ホセ。 Fiol, Miquel (1985)、「高密度複合グラフ」、Ars Combinatoria、20 : 211–237
  • モロツォフ、セルゲイ（2006）、情報伝達と組合せ論の一般理論、シュプリンガー、pp.  853– 857、ISBN 978-3-540-46244-6
  • サンプルズ、マイケル (1997)、「小さな直径を持つ大きなネットワーク」、グラフ理論の概念、コンピュータサイエンスの講義ノート、第1335巻、シュプリンガー、ベルリン、ハイデルベルク、pp.  288– 302、doi : 10.1007/BFb0024505、ISBN 978-3-540-69643-8
  • ストウィック、ロバート（1970）、「（d, k）グラフの改良構築手法」、IEEE Transactions on Computers、C-19（12）：1214–1216、doi：10.1109/TC.1970.222861
「 https://en.wikipedia.org/w/index.php?title=Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree&oldid=1308092056」より取得