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

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

3-регулярный граф Клейна — кубический граф с 56 вершинами и 84 рёбрами; назван по имени Феликса Клейна с двойственным ему 7-регулярным графом.

Граф гамильтонов, имеет хроматическое число 3, хроматический индекс 3, радиус 6, диаметр 6 и обхват 7. Является также вершинно 3-связным и рёберно 3-связным. Имеет толщину книги 3 и Число очередей 2.

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

Граф, как и двойственный ему 7-регулярный, можно вложить в ориентируемую поверхность рода 3, где он образует карту с 24 семиугольными гранями. Символ Шлефли — {7,3}₈.

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

Может быть получен из графа Коксетера с 28 вершинами.

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

Характеристическим многочленом этого графа с 56 вершинами является:

[math]\displaystyle{ x^7 \,(x-3)\,(x+2)^6 \left(x^2-2\right)^6 \left(x^2+x-4\right)^7 \left(x^2-2 x-1\right)^8 }[/math].

Квартика Клейна с 24 семиугольниками

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

Литература

• Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).
• Conder M., Dobcsányi P. Trivalent symmetric graphs up to 768 vertices // J. Combin. Math. Combin. Comput.. — 2002. — Т. 40. — С. 41–63.
• Italo Dejter. From the Coxeter graph to the Klein graph // CiteSeer. — 2010. — arXiv:1002.1960.
• Egon Schulte, Wills J. M. A Polyhedral Realization of Felix Klein's Map {3, 7}₈ on a Riemann Surface of Genus 3 // J. London Math. Soc.. — 1985. — Т. s2-32, вып. 3. — С. 539–547. — doi:10.1112/jlms/s2-32.3.539.
• Andries Brouwer, Arjeh Cohen, Arnold Neumaier. Distance-Regular Graphs. — Springer-Verlag, 1989. — С. 398. — ISBN 978-0-387-50619-7.
• van Dam E. R., Haemers W. H., Koolen J. H., Spence E. Characterizing distance-regularity of graphs by the spectrum // J. Combin. Theory Ser. A. — 2006. — Т. 113, вып. 8. — С. 1805–1820. — doi:10.1016/j.jcta.2006.03.008.