Таблица вершинно-симметричных орграфов - Table of vertex-symmetric digraphs
Самый известный вершинно-транзитивный диграфы (по состоянию на октябрь 2008 г.) в направленном Проблема диаметра градуса приведены в таблице ниже.
Таблица порядков наибольших известных вершинно-симметричных графов для задачи направленного диаметра степеней
k d | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 6 | 10 | 20 | 27 | 72 | 144 | 171 | 336 | 504 | 737 |
| 3 | 12 | 27 | 60 | 165 | 333 | 1 152 | 2 041 | 5 115 | 11 568 | 41 472 |
| 4 | 20 | 60 | 168 | 465 | 1 378 | 7 200 | 14 400 | 42 309 | 137 370 | 648 000 |
| 5 | 30 | 120 | 360 | 1 152 | 3 775 | 28 800 | 86 400 | 259 200 | 1 010 658 | 5 184 000 |
| 6 | 42 | 210 | 840 | 2 520 | 9 020 | 88 200 | 352 800 | 1 411 200 | 5 184 000 | 27 783 000 |
| 7 | 56 | 336 | 1 680 | 6 720 | 20 160 | 225 792 | 1 128 960 | 5 644 800 | 27 783 000 | 113 799 168 |
| 8 | 72 | 504 | 3 024 | 15 120 | 60 480 | 508 032 | 3 048 192 | 18 289 152 | 113 799 168 | 457 228 800 |
| 9 | 90 | 720 | 5 040 | 30 240 | 151 200 | 1 036 800 | 7 257 600 | 50 803 200 | 384 072 192 | 1 828 915 200 |
| 10 | 110 | 990 | 7 920 | 55 400 | 332 640 | 1 960 200 | 15 681 600 | 125 452 800 | 1 119 744 000 | 6 138 320 000 |
| 11 | 132 | 1 320 | 11 880 | 95 040 | 665 280 | 3 991 680 | 31 152 000 | 282 268 800 | 2 910 897 000 | 18 065 203 200 |
| 12 | 156 | 1 716 | 17 160 | 154 440 | 1 235 520 | 8 648 640 | 58 893 120 | 588 931 200 | 6 899 904 000 | 47 703 427 200 |
| 13 | 182 | 2 184 | 24 024 | 240 240 | 2 162 160 | 17 297 280 | 121 080 960 | 1 154 305 152 | 15 159 089 098 | 115 430 515 200 |
Ключ к цветам
| цвет | подробности |
|---|---|
| * | Семейство орграфов, обнаруженных В. Х. Каутцем. Подробнее читайте в статье автора. |
| * | Семейство орграфов, обнаруженных В. Фабером и Дж. В. Муром. Более подробная информация доступна и у других авторов. |
| * | Диграф, найденный В. Фабером и Дж. В. Муром. Полный набор орграфов Кэли в таком порядке был обнаружен Эялем Лозом. |
| * | Диграфы, найденные Франсеском Комельясом и М.А. Фиолом. Подробнее читайте в статье авторов. |
| * | Диграфы Кэли, найденные Майклом Дж. Диннином. Подробности об этом графике доступны в статье автора. |
| * | Диграфы Кэли, найденные Майклом Дж. Диннином. Полный набор орграфов Кэли в таком порядке был обнаружен Эялем Лозом. |
| * | Диграфы Кэли, найденные Полом Хафнером. Подробности об этом графике доступны в статье автора. |
| * | Диграф Кэли, найденный Полом Хафнером. Полный набор орграфов Кэли в таком порядке был обнаружен Эялем Лозом. |
| * | Диграфы, найденные Х. Гомесом. |
| * | Диграфы Кэли, найденные Эялем Лозом. Более подробная информация доступна в статье Эяля Лоза и Йозефа Шираня. |
использованная литература
- Каутц, W.H. (1969), «Проектирование оптимальных сетей межсетевого взаимодействия для мультипроцессоров», Архитектура и дизайн цифровых компьютеров, Летний институт повышения квалификации НАТО: 249–272
- Faber, V .; Мур, Дж. (1988), "Сети межсоединений малого диаметра высокой степени с вершинной симметрией: направленный случай", Технический отчет LA-UR-88-1051, Национальная лаборатория Лос-Аламоса
- Дж. Диннин, Майкл; Хафнер, Пол Р. (1994), "Новые результаты для задачи степени / диаметра", Сети, 24 (7): 359–367, arXiv:математика / 9504214, Дои:10.1002 / нетто.3230240702
- Comellas, F .; Фиол, М.А. (1995), "Вершинно-симметричные орграфы малого диаметра", Дискретная прикладная математика, 58 (1): 1–12, Дои:10.1016 / 0166-218X (93) E0145-O
- Миллер, Мирка; Ширан, Йозеф (2005), «Графы Мура и не только: обзор проблемы степени / диаметра» (PDF), Электронный журнал комбинаторики, Динамический, опрос D
- Лоз, Эял; Ширань, Йозеф (2008), «Новые рекордные графы в задаче градус-диаметр» (PDF), Австралазийский журнал комбинаторики, 41: 63–80
внешние ссылки
- Вершинно-симметричные орграфы онлайн-стол.
- Проблема степени - диаметра на CombinatoricsWiki.org.
- Эяля Лоза Страница задачи "Градус-диаметр".