В математической области теории графов , то граф Дейка является 3- регулярного графа с 32 вершинами и 48 ребер, названных в честь Вальтера фон Дейка . [1] [2]
Граф Дика | |
---|---|
Названный в честь | В. Дайк |
Вершины | 32 |
Края | 48 |
Радиус | 5 |
Диаметр | 5 |
Обхват | 6 |
Автоморфизмы | 192 |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Толщина книги | 3 |
Номер очереди | 2 |
Характеристики | Симметричный кубический гамильтонов двудольный граф Кэли |
Таблица графиков и параметров |
Это гамильтониан с 120 различными гамильтоновыми циклами. Он имеет хроматическое число 2, хроматический индекс 3, радиус 5, диаметр 5 и обхват 6. Это также 3- вершинно-связный и 3 -реберный граф. Он имеет книжную толщину 3 и номер очереди 2. [3]
Граф Дика является тороидальным графом , а двойственным ему симметричным тороидальным вложением является граф Шриханде , сильно регулярный граф, как симметричный, так и гамильтониан.
Алгебраические свойства
Группа автоморфизмов графа Дика - это группа порядка 192. [4] Она действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Дика является симметричным графом . У него есть автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. Согласно переписи населения Фостера , граф Дика, обозначаемый как F32A, является единственным кубическим симметричным графом с 32 вершинами. [5]
Характеристический полином графа Dyck равен.
Карта Дика
График Дейка является скелетом из симметричной тесселяции поверхности из рода три на двенадцать восьмиугольников, известных как карты Дейка или Dyck черепице . Два графиком для этой плитки является полным трехсторонний графом К 4,4,4 . [6] [7]
Галерея
Альтернативный рисунок графа Дика.
Хроматического числа графа Dyck 2.
Хроматической индекс графа Dyck равен 3.
Рекомендации
- ↑ Dyck, W. (1881), "Uber Aufstellung und Untersuchung von Gruppe und Irrationalität Regärer Riemann'scher Flächen" , Math. Аня. , 17 : 473, DOI : 10.1007 / bf01446929.
- ^ Вайсштейн, Эрик В. «График Дика» . MathWorld .
- ^ Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Ройл, Г. Данные F032A [ постоянная мертвая ссылка ]
- ^ Кондер, М .; Добчаньи, П. (2002), "Трехвалентные симметрические графы до 768 вершин", J. Combin. Математика. Комбинировать. Comput. , 40 : 41–63.
- ^ Dyck, W. (1880), "Notiz über eine Regäre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung" , Math. Аня. , 17 : 510-516, DOI : 10.1007 / bf01446930.
- ^ Ceulemans, А. (2004), "О tetrakisoctahedral группы графа Dyck и его молекулярной реализации.", Молекулярная физика , 102 (11): 1149-1163, DOI : 10,1080 / +00268970410001728780.