Графы Клейна

Поверхность рода 3

В математической области теории графов графы Клейна — это два разных , но связанных регулярных графа , каждый из которых имеет 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-вершинного графа Клейна равен ${\displaystyle 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}}$

7-регулярный граф Клейна

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

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

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

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

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

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

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

Квартик Клейна, замощенный 56 треугольниками (дуальный к карте Клейна)

Ссылки

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 .