В математической области теории графов , то графы Клейна две различные , но связанные с ними регулярные графы , каждый с 84 ребрами. Каждый из них может быть встроен в ориентируемой поверхности из рода 3, в котором они образуют двойные графики .
Кубический граф Клейна
(Кубический) граф Клейна | |
---|---|
Названный в честь | Феликс Кляйн |
Вершины | 56 |
Края | 84 |
Радиус | 6 |
Диаметр | 6 |
Обхват | 7 |
Автоморфизмы | 336 |
Хроматическое число | 3 |
Хроматический индекс | 3 |
Толщина книги | 3 |
Номер очереди | 2 |
Характеристики | Симметричный кубический гамильтонов граф Кэли |
Таблица графиков и параметров |
Этот граф является 3- регулярным графом с 56 вершинами и 84 ребрами, названным в честь Феликса Клейна .
Это гамильтонов граф . Он имеет хроматическое число 3, хроматический индекс 3, радиус 6, диаметр 6 и обхват 7. Это также 3- вершинно-связный и 3 -реберный граф. Он имеет книжную толщину 3 и номер очереди 2. [1]
Его можно вложить в ориентируемую поверхность рода -3 (которую можно представить как квартику Клейна ), где он образует «карту Клейна» с 24 семиугольными гранями, символом Шлефли {7,3} 8 .
Согласно переписи населения Фостера , граф Клейна, обозначенный как F056B, является единственным кубическим симметричным графом с 56 вершинами, который не является двудольным . [2]
Его можно вывести из 28-вершинного графа Кокстера . [3]
Алгебраические свойства
Группа автоморфизмов графа Клейна - это группа PGL 2 (7) порядка 336, в которой PSL 2 (7) является нормальной подгруппой. Эта группа действует транзитивно на своих полуребрах, поэтому граф Клейна является симметричным графом .
Характеристический полином этого 56-вершин графа Клейна равна
Галерея
Альтернативный рисунок кубического графа Клейна, показывающий, что он гамильтонов, с хроматическим индексом 3.
7-валентный граф Клейна
(7-валентный) граф Клейна | |
---|---|
Названный в честь | Феликс Кляйн |
Вершины | 24 |
Края | 84 |
Радиус | 3 |
Диаметр | 3 |
Обхват | 3 |
Автоморфизмы | 336 |
Хроматическое число | 4 |
Хроматический индекс | 7 |
Характеристики | Симметричный гамильтониан |
Таблица графиков и параметров |
Этот граф представляет собой 7- регулярный граф с 24 вершинами и 84 ребрами, названный в честь Феликса Клейна .
Это гамильтонов граф . Он имеет хроматическое число 4, хроматический индекс 7, радиус 3, диаметр 3 и обхват 3.
Он может быть вложен в ориентируемую поверхность рода 3, где он образует двойственную «карту Клейна» с 56 треугольными гранями, символ Шлефли {3,7} 8 . [4]
Это уникальный дистанционно регулярный граф с массивом пересечений; однако это не дистанционно-транзитивный граф . [5]
Алгебраические свойства
Группа автоморфизмов 7-валентного графа Клейна - это та же группа порядка 336, что и для кубического отображения Клейна, аналогичным образом действующая транзитивно на его полуребрах.
Характеристический полином этого 24-вершин графа Клейна равна. [6]
Рекомендации
- ^ Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Кондер, М .; Dobcsányi, P. (2002), "Трехвалентные симметрические графы до 768 вершин", J. Combin. Математика. Комбинировать. Comput. , 40 : 41–63.
- ^ Дейтер, Итало. «От графа Кокстера к графу Клейна». CiteSeer. CiteSeerX 10.1.1.188.2580 . Цитировать журнал требует
|journal=
( помощь ) - ^ Шульте, Эгон; Уиллс, Дж. М. (1985). "Полиэдральная реализация отображения Феликса Клейна {3, 7} 8 на римановой поверхности рода 3" . J. London Math. Soc . s2-32 (3): 539–547. DOI : 10,1112 / jlms / s2-32.3.539 .
- ^ Брауэр, Андрис ; Коэн, Арджех; Ноймайер, Арнольд (1989). Дистанционно регулярные графы . Springer-Verlag . п. 386 . ISBN 978-0-387-50619-7.
- ^ ван Дам, скорая помощь; Хемерс, WH; Кулен, JH; Спенс, Э. (2006). «Характеризация дистанционной регулярности графов спектром» . J. Combin. Теория Сер. . 113 (8): 1805–1820. DOI : 10.1016 / j.jcta.2006.03.008 .