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

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

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

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

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

Примечания

Литература

• 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 : .
• Egon Schulte, Wills J. M. // J. London Math. Soc.. — 1985. — Т. s2-32 , вып. 3 . — С. 539–547 . — doi : .
• Andries Brouwer, Arjeh Cohen, Arnold Neumaier. . — 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 : .