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

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

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

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

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

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

Характеристический многочлен — ${\displaystyle (x-7)(x+1)^{7}(x^{2}-7)^{8}}$[3].

Квартика Клейна^[англ.] с 56 треугольниками

Примечания

1. Schulte, Wills, 1985, с. 539–547.
2. Brouwer, Cohen, Neumaier, 1989, с. 386.
3. van Dam, Haemers, Koolen, Spence, 2006, с. 1805–1820.

Литература

• 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.