Таблица вершинно-симметричных орграфов
Наиболее известные вершинные транзитивные орграфы (по состоянию на октябрь 2008 г.) в направленной задаче о градусном диаметре сведены в таблицу ниже.
Таблица порядков крупнейших известных вершинно-симметричных графов для направленной задачи степенного диаметра
[ редактировать ]к д |
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 |
Ключ к цветам
[ редактировать ]| Цвет | Подробности |
|---|---|
| * | Семейство диграфов, найденное WHKautz. Более подробную информацию можно найти в статье автора. |
| * | Семейство диграфов, найденное В.Фабером и Дж.В.Муром. Более подробную информацию можно найти и у других авторов. |
| * | Диграф найден В.Фабером и Дж.В.Муром. Полный набор орграфов Кэли в этом порядке был найден Эялем Лозом. |
| * | Диграфы найдены Франческом Комелласом и М.А. Фиолем. Более подробную информацию можно найти в статье авторов. |
| * | Диграфы Кэли, найденные Майклом Дж. Диннином. Подробности об этом графике доступны в статье автора. |
| * | Диграфы Кэли, найденные Майклом Дж. Диннином. Полный набор орграфов Кэли в этом порядке был найден Эялем Лозом. |
| * | Диграфы Кэли, найденные Полом Хафнером. Подробности об этом графике доступны в статье автора. |
| * | Диграф Кэли, найденный Полом Хафнером. Полный набор орграфов Кэли в этом порядке был найден Эялем Лозом. |
| * | Диграфы найдены Дж. Гомесом. |
| * | Диграфы Кэли, найденные Эялем Лозом. Более подробную информацию можно найти в статье Эяля Лоза и Йозефа Ширана. |
Ссылки
[ редактировать ]- Каутц, WH (1969), «Проектирование оптимальных сетей межпроцессорного взаимодействия для мультипроцессоров», Архитектура и проектирование цифровых компьютеров, Летний институт НАТО : 249–272.
- Фабер, В.; Мур, Дж. В. (1988), «Сети межсоединений высокой степени малого диаметра с вершинной симметрией: направленный случай», Технический отчет LA-UR-88-1051, Национальная лаборатория Лос-Аламоса.
- Дж. Диннин, Майкл; Хафнер, Пол Р. (1994), «Новые результаты для проблемы степени/диаметра», Networks , 24 (7): 359–367, arXiv : math/9504214 , doi : 10.1002/net.3230240702
- Комеллас, Ф.; Фиол, Массачусетс (1995), «Вершинно-симметричные орграфы малого диаметра», Discrete Applied Mathematics , 58 (1): 1–12, doi : 10.1016/0166-218X(93)E0145-O
- Миллер, Мирка ; Ширань, Йозеф (2005), «Графы Мура и не только: обзор проблемы степени/диаметра» (PDF) , Электронный журнал комбинаторики , Динамика, обзор D
- Лоз, Эяль; Ширань, Йозеф (2008), «Новые графы рекордов в проблеме степени-диаметра» (PDF) , Австралазийский журнал комбинаторики , 41 : 63–80
Внешние ссылки
[ редактировать ]- вершинно-симметричных орграфов . Онлайн-таблица
- Проблема степени-диаметра на CombinatoricsWiki.org .
- Страница задачи Эяля Лоза «Градус-диаметр».