Графы Клейна

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

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

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

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

Это 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-вершинного графа Клейна равен $x^{7}\,(x-3)\,(x+2)^{6}\left(x^{2}-2\right)^{6}\left(x^{2}+x-4\right)^{7}\left(x^{2}-2x-1\right)^{8}$

В гамильтоновом пути , нарисованном тремя цветами ребер (показывает, что хроматический индекс равен 3)

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}$

Ссылки

^ Вольц, Джессика; Проектирование линейных макетов с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
^ Кондер, М .; Добчани, П. (2002). «Трёхвалентные симметричные графы до 768 вершин». J. Combin. Math. Combin. Comput . 40 : 41–63 ..
^ Дейтер, Итало Дж. (2012). «От графа Кокстера к графу Клейна». Журнал теории графов . 70 (1): 1–9 . arXiv : 1002.1960 . дои : 10.1002/jgt.20597. МР 2916063.
^ Шульте, Эгон; Уиллс, Дж. М. (1985). «Полиэдральная реализация отображения Феликса Клейна {3, 7}8 на римановой поверхности рода 3». J. London Math. Soc . s2-32 (3): 539– 547. doi :10.1112/jlms/s2-32.3.539.
^ Брауэр, Андриес ; Коэн, Арье; Ноймайер, Арнольд (1989). Дистанционно-регулярные графы . Спрингер-Верлаг . п. 386. ИСБН 978-0-387-50619-7.
^ van Dam, ER; Haemers, WH; Koolen, JH; Spence, E. (2006). «Характеристика дистанционной регулярности графов с помощью спектра». J. Combin. Theory Ser. A . 113 (8): 1805– 1820. doi : 10.1016/j.jcta.2006.03.008 .

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

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

[3] Дейтер, Итало Дж. (2012). «От графа Кокстера к графу Клейна». Журнал теории графов . 70 (1): 1–9 . arXiv : 1002.1960 . дои : 10.1002/jgt.20597. МР 2916063.

[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). Дистанционно-регулярные графы . Спрингер-Верлаг . п. 386. ИСБН 978-0-387-50619-7.

[6] van Dam, ER; Haemers, WH; Koolen, JH; Spence, E. (2006). «Характеристика дистанционной регулярности графов с помощью спектра». J. Combin. Theory Ser. A . 113 (8): 1805– 1820. doi : 10.1016/j.jcta.2006.03.008 .