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

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

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

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

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

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

ПримечанияПравить

↑ Schulte, Wills, 1985, с. 539–547.
↑ Brouwer, Cohen, Neumaier, 1989, с. 386.
↑ 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.

[_c9f0496e93c24299-1] Schulte, Wills, 1985, с. 539–547.

[_ce01c21ffd6aad1c-2] Brouwer, Cohen, Neumaier, 1989, с. 386.

[_1f29ca66f6759279-3] van Dam, Haemers, Koolen, Spence, 2006, с. 1805–1820.

[1]

[2]

[3]