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[1].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f0/Triple_torus_illustration.png/150px-Triple_torus_illustration.png)
Граф, как и двойственный ему 7-регулярный, можно вложить в ориентируемую поверхность рода 3, где он образует карту с 24 семиугольными гранями. Символ Шлефли — {7,3}8.
Согласно списку Фостера, где граф обозначен как F056B, является единственным кубическим симметричным графом с 56 вершинами, который не является двудольным[2].
Может быть получен из графа Коксетера с 28 вершинами[3].
Группой автоморфизмов 3-регулярного графа Клейна является группа PGL2(7) порядка 336, которая имеет PSL2(7) в качестве нормальной подгруппы. Эта группа действует транзитивно на полурёбра, так что граф Кляйна является симметричным.
Характеристическим многочленом этого графа с 56 вершинами является:
- .
![]() |
![]() |
Примечания
[править | править код]- ↑ Wolz, 2018.
- ↑ Conder, Dobcsányi, 2002, с. 41–63.
- ↑ Dejter, 2010.
Литература
[править | править код]- 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}8 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.
Для улучшения этой статьи желательно:
|