Графы Клейна

В математической области теории графов , то графы Клейна две различные , но связанные с ними регулярные графы , каждый с 84 ребрами. Каждый из них может быть встроен в ориентируемой поверхности из рода 3, в котором они образуют двойные графики .

Кубический граф Клейна

(Кубический) граф Клейна
Граф 56-Клейна
Названный в честь	Феликс Кляйн
Вершины	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} ₈ .

Согласно переписи населения Фостера , граф Клейна, обозначенный как F056B, является единственным кубическим симметричным графом с 56 вершинами, который не является двудольным . ^[2]

Его можно вывести из 28-вершинного графа Кокстера . ^[3]

Алгебраические свойства

Группа автоморфизмов графа Клейна - это группа PGL ₂ (7) порядка 336, в которой PSL ₂ (7) является нормальной подгруппой. Эта группа действует транзитивно на своих полуребрах, поэтому граф Клейна является симметричным графом .

Характеристический полином этого 56-вершин графа Клейна равна ${\ Displaystyle х ^ {7} \, (х-3) \, (х + 2) ^ {6} \ влево (х ^ {2} -2 \ вправо) ^ {6} \ влево (х ^ {2 } + x-4 \ right) ^ {7} \ left (x ^ {2} -2x-1 \ right) ^ {8}}$

Галерея

Альтернативный рисунок кубического графа Клейна, показывающий, что он гамильтонов, с хроматическим индексом 3.

7-валентный граф Клейна

(7-валентный) граф Клейна
Граф 24-Клейна
Названный в честь	Феликс Кляйн
Вершины	24
Края	84
Радиус	3
Диаметр	3
Обхват	3
Автоморфизмы	336
Хроматическое число	4
Хроматический индекс	7
Характеристики	Симметричный гамильтониан
Таблица графиков и параметров

Этот граф представляет собой 7- регулярный граф с 24 вершинами и 84 ребрами, названный в честь Феликса Клейна .

Это гамильтонов граф . Он имеет хроматическое число 4, хроматический индекс 7, радиус 3, диаметр 3 и обхват 3.

Он может быть вложен в ориентируемую поверхность рода 3, где он образует двойственную «карту Клейна» с 56 треугольными гранями, символ Шлефли {3,7} ₈ . ^[4]

Это уникальный дистанционно регулярный граф с массивом пересечений ; однако это не дистанционно-транзитивный граф . ^[5] $\{7,4,1;1,2,7\}$

Алгебраические свойства

Группа автоморфизмов 7-валентного графа Клейна - это та же группа порядка 336, что и для кубического отображения Клейна, аналогичным образом действующая транзитивно на его полуребрах.

Характеристический полином этого 24-вершин графа Клейна равно . ^[6] $(x-7)(x+1)^{7}(x^{2}-7)^{8}$

использованная литература

^ Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
^ Кондер, М .; Добчаньи, П. (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.
^ Ван Дам, ER; Хемерс, WH; Кулен, JH; Спенс, Э. (2006). «Характеризация дистанционной регулярности графов спектром» . J. Combin. Теория Сер. . 113 (8): 1805–1820. DOI : 10.1016 / j.jcta.2006.03.008 .

[1] Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.

[2] Кондер, М .; Добчаньи, П. (2002), "Трехвалентные симметрические графы до 768 вершин", J. Combin. Математика. Комбинировать. Comput. , 40 : 41–63.

[3] Дейтер, Итало. «От графа Кокстера к графу Клейна». CiteSeer. CiteSeerX 10.1.1.188.2580 . Цитировать журнал требует |journal=( помощь )

[4] Шульте, Эгон; Уиллс, Дж. М. (1985). "Полиэдральная реализация отображения Феликса Клейна {3, 7} 8 на римановой поверхности рода 3" . J. London Math. Soc . s2-32 (3): 539–547. DOI : 10,1112 / jlms / s2-32.3.539 .

[5] Брауэр, Андрис ; Коэн, Арджех; Ноймайер, Арнольд (1989). Дистанционно регулярные графы . Springer-Verlag . п. 386 . ISBN 978-0-387-50619-7.

[6] Ван Дам, ER; Хемерс, WH; Кулен, JH; Спенс, Э. (2006). «Характеризация дистанционной регулярности графов спектром» . J. Combin. Теория Сер. . 113 (8): 1805–1820. DOI : 10.1016 / j.jcta.2006.03.008 .

[1]