Таблица крупнейших известных графов заданного диаметра и максимальной степени

В теории графов проблема диаметра степени — это проблема нахождения наибольшего возможного графа для заданной максимальной степени и диаметра . Граница Мура устанавливает ограничения на это, но в течение многих лет математики в этой области интересовались более точным ответом. В таблице ниже представлен текущий прогресс по этой проблеме (исключая случай степени 2, где наибольшие графы — это циклы с нечетным числом вершин).

Таблица порядков крупнейших известных графов для неориентированной задачи диаметра степени

Ниже приведена таблица номеров вершин для наиболее известных графов (по состоянию на июнь 2024 года) в неориентированной задаче диаметра степени для графов степени не более 3 ≤  d  ≤ 16 и диаметра 2 ≤  k  ≤ 10. Известно, что только несколько графов в этой таблице (отмечены жирным шрифтом) являются оптимальными (то есть максимально возможными). Остальные являются просто наибольшими из обнаруженных на данный момент, и, таким образом, нахождение большего графа, который по порядку (с точки зрения размера множества вершин) ближе к границе Мура, считается открытой проблемой . Некоторые общие конструкции известны для значений d и k за пределами диапазона, указанного в таблице.

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

Записи без сноски были найдены Loz & Širáň (2008). Во всех остальных случаях сноски в таблице указывают на происхождение графа, который достигает заданного числа вершин:

  1. ^ Граф Петерсена .
  2. ^ abc Оптимальные графы, доказанные Элспасом (1964).
  3. ^ Оптимальный граф, найденный Доти (1982) и доказанный Бусетом (2000).
  4. ^ График найден Алегре, Фиолем и Йеброй (1986).
  5. ^ abcdefghi Графики, найденные Джеффри Эксу с 1998 по 2010 год.
  6. ^ График найден Цзяньсяном Ченом в 2018 году.
  7. ^ График найден Кондером (2006).
  8. ^ График найден Оллрайтом (1992).
  9. ^ abcd Графики, найденные Делормом (1985a).
  10. ^ График найден Комелласом и Гомесом (1994).
  11. ^ abcde Графики, найденные Пинедой-Вильявисенсио и др. (2006).
  12. ^ Оптимальный граф, найденный Вегнером (1977) и доказанный Молодцовым (2006).
  13. ^ abcdefghijkl Графики найдены Comellas (2024).
  14. ^ abc Графики найдены Канале и Родригесом (2012).
  15. ^ Граф Хоффмана–Синглтона .
  16. ^ График найден Сэмпелсом (1997).
  17. ^ График найден Диннином и Хафнером (1994).
  18. ^ abc Графики, найденные Сторвиком (1970).
  19. ^ График найден Маргаридой Митхана и Франческом Комелласом в 1995 году и независимо Сампелсом (1997).
  20. ^ abcd Графики, найденные Гомесом (2009).
  21. ^ abcdefghi Графики, найденные Гомесом и Фиолем (1985).
  22. ^ ab Графики, найденные Делормом и Фархи (1984).
  23. ^ График найден Бермондом, Делормом и Фархи (1982).
  24. ^ Графики Маккея-Миллера-Ширана, найденные Маккеем, Миллером и Шираном (1998).
  25. ^ График найден Владом Пелахаты в 2021 году.
  26. ^ ab Графики найдены Гомесом, Фиолем и Серрой (1993).
  27. ^ График найден Эдуардо А. Канале в 2012 году.
  28. ^ abc Графики, найденные Делормом (1985b).
  29. ^ График найден Абасом (2016).

Ссылки

  • Алегре, Игнасио; Фиоль, Микель; Йебра, Дж. Луис А. (1986), «Некоторые большие графы с заданной степенью и диаметром», Журнал теории графов , 10 (2): 219–224 , doi : 10.1002/jgt.3190100211
  • Бермонд, Жан-Клод; Делорм, Чарльз; Фархи, Гай (1982), «Большие графы с заданной степенью и диаметром III» (PDF) , Annals of Discrete Mathematics , North-Holland Mathematics Studies, 13 : 23– 31, doi :10.1016/S0304-0208(08)73544-8, ISBN 9780444864499, S2CID  118362048
  • Канале, Эдуардо; Родригес, Алексис (2012), О применении графиков напряжения к проблеме степени/диаметра (PDF) , заархивировано из оригинала (PDF) 28.09.2020
  • Комеллас, Франческ; Гомес, Хосе (1994). «Новые большие графы с заданной степенью и диаметром». arXiv : математика/9411218 .
  • Комеллас, Франческ (2024). "Таблица больших графов с заданной степенью и диаметром". arXiv : 2406.18994 .
  • Кондер, Марстон (2006). «Трёхвалентные (кубические) симметричные графы с числом вершин до 2048».
  • Делорм, Чарльз; Фархи, Гай (1984), «Большие графы с заданной степенью и диаметром. Часть I», IEEE Transactions on Computers , 33 (9): 857– 860, doi :10.1109/TC.1984.1676504
  • Делорм, Чарльз (1985b), «Большие двудольные графы с заданной степенью и диаметром», Журнал теории графов , 9 (3): 325–334 , doi :10.1002/jgt.3190090304, S2CID  21199003
  • Диннин, Майкл Дж.; Хафнер, Пол Р. (1994), «Новые результаты для проблемы степени/диаметра», Networks , 24 (7): 359–367 , arXiv : math/9504214 , doi :10.1002/net.3230240702, S2CID  26375247
  • Доти, Карл (1982), «Большие регулярные сети взаимосвязей», Труды 3-й Международной конференции по распределенным вычислительным системам , IEEE Computer Society, стр.  312–317
  • Элспас, Бернард (1964), «Топологические ограничения на логику с ограниченной взаимосвязью», Труды Пятого ежегодного симпозиума по теории коммутационных схем и логическому проектированию 1964 года , стр.  133–137 , doi :10.1109/SWCT.1964.27
  • Гомес, Хосе (2009), «Некоторые новые большие (Δ, 3)-графы», Networks , 53 (1): 1– 5, doi :10.1002/NET.V53:1
  • Гомес, Хосе; Фиол, Микель (1985), «Плотные составные графы», Ars Combinatoria , 20 : 211–237 .
  • Гомес, Хосе; Фиоль, Микель; Серра, Ориол (1993), «О больших (Δ,D)-графах», Discrete Mathematics , 114 ( 1–3 ): 219–235 , doi : 10.1016/0012-365X(93)90368-4
  • Хоффман, Алан Дж.; Синглтон, Роберт Р. (1960), «Графы Мура с диаметром 2 и 3», IBM Journal of Research and Development , 5 (4): 497– 504, doi :10.1147/rd.45.0497, MR  0140437
  • Лоз, Эяль; Ширань, Йозеф ( 2008 ), «Новые графы рекордов в задаче о степени-диаметре» (PDF) , Australasian Journal of Combinatorics , 41 : 63–80
  • Молодцов, Сергей (2006), Общая теория передачи информации и комбинаторика , стр.  853–857 , ISBN 978-3-540-46244-6
  • Пинеда-Вильявисенсио, Гильермо; Гомес, Хосе; Миллер, Мирка; Перес-Росес, Эберт (2006), «Новые наибольшие графики диаметра 6», Электронные заметки по дискретной математике , 24 : 153–160 , doi : 10.1016/j.endm.2006.06.044, hdl : 1959.17/67691
  • Сэмпелс, Михаэль (1997), «Большие сети с малым диаметром», Графовые концепции в информатике , Lecture Notes in Computer Science, т. 1335, Springer, Берлин, Гейдельберг, стр.  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
  • Вегнер, Герд (1977), Графы с заданным диаметром и задача раскраски (PDF) , Technische Universität Dortmund, doi : 10.17877/DE290R-16496
  • Проблема степени-диаметра на CombinatoricsWiki.org.
  • Страница задачи Эяла Лоза о степени и диаметре (архив 2016 г.)
  • Страница Джеффри Эксу с графиками записи градус-диаметр (архив 2015 г.)
  • Страница исследований Гильермо Пинеда-Вильявисенсио.
Взято с "https://en.wikipedia.org/w/index.php?title=Таблица_наибольшего_известного_графика_заданного_диаметра_и_максимальной_степени&oldid=1273130587"