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

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

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

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

Может быть получен из графа Коксетера с 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}}$ .

Примечания

Литература

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