| 110-вершинный граф Иванова — Иофиновой | |
|---|---|
| Вершин | 110 |
| Рёбер | 165 |
| Радиус | 7 |
| Диаметр | 7 |
| Обхват | 10 |
| Автоморфизмы | 1320 (PGL2(11)) |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Свойства |
Полусимметричный Двудольный Кубический Гамильтонов |
110-вершинный граф Иванова — Иофиновой — полусимметричный кубический граф с 110 вершинами и 165 рёбрами.
Свойства
Иванов и Иофинова доказали в 1985 году существование пяти и только пяти полусимметричных кубических двудольных графов, группы автоморфизмов которых действуют примитивно на каждой доле двудольного графа[1]. Наименьший такой граф имеет 110 вершин. Остальные четыре имеют 126, 182, 506 и 990 вершин[2]. 126-вершинный граф Иванова — Иофиновой известен также как 12-клетка Татта.
Диаметр 110-вершинного графа Иванова — Иофиновой (наибольшее расстояние между любой парой вершин) равен 7. Радиус его равен также 7. Его обхват равен 10.
Граф 3-связен и рёберно 3-связен — чтобы сделать его несвязным, нужно удалить по меньшей мере три ребра или три вершины.
Раскраска
Хроматическое число 110-вершинного графа Иванова — Иофиновой равно 2 — его вершины можно раскрасить в два цвета так, что никакие две вершины одного цвета не соединяются ребром. Его хроматический индекс равен 3 — рёбра графа можно выкрасить в 3 цвета так, что никакие два ребра одного цвета не сходятся в одной вершине.
Алгебраические свойства
Характеристический многочлен графа равен . Группа симметрии является проективной группой PGL2(11) с 1320 элементами[3].
Полусимметрия
Немногие графы показывают полусимметрию — большинство рёберно-транзитивных графов также и вершинно-транзитивны. Самым маленьким полусимметричным графом является граф Фолкмана с 20 вершинами, который является 4-регулярным. Три наименьших кубических полусимметричных графа — это граф Грея с 54 вершинами, этот наименьший из графов Иванова — Иофиновой с 110 вершинами и граф Любляны с 112 вершинами[4][5].
Примечания
- ↑ Han and Lu Affine primitive groups and Semisymmetric graphs. combinatorics.org. Дата обращения: 12 августа 2015. Архивировано 3 октября 2018 года.
- ↑ Weisstein, Eric Iofinova-Ivanov Graphs. Wolfram MathWorld. Wolfram. Дата обращения: 11 августа 2015. Архивировано 19 января 2019 года.
- ↑ Iofinova, Ivanov, 2013, с. 470.
- ↑ Conder, Malnič, Marušič, Pisanski, Potočnik, 2002.
- ↑ Conder, Malnič, Marušič, Potočnik, 2006, с. 255–294.
Литература
- Iofinova M. E., Ivanov A. A. Investigations in Algebraic Theory of Combinatorial Objects / I. A. Faradžev, A. A. Ivanov, M. H. Klin, A. J. Woldar. — publisher=Springer-Science+Business Media, B.V., 2013. — Т. 94. — (Mathematics and Its Applications, Soviet series). — ISBN 978-90-481-4195-1. — ISBN 978-94-017-1972-8. Перевод книги
- Исследования по алгебраической теории комбинаторных объектов : Тр. Семинара / Отв. ред. М. Х. Клин, И. А. Фараджев. — М.: ВНИИСИ, 1985. — Т. 185.
- Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph // IMFM Preprints. — Ljubljana: Institute of Mathematics, Physics and Mechanics, 2002. — Т. 40, вып. 845.
- Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. A census of semisymmetric cubic graphs on up to 768 vertices // Journal of Algebraic Combinatorics. — 2006. — Т. 23. — С. 255–294. — doi:10.1007/s10801-006-7397-3.
- Иванов А. A., Иофинова М. E. Бипримитивные кубические графы // Исследования по алгебраической теории комбинаторных объектов. — М., 1985. — С. 137–152. — (Серия: ВНИИ системных исследований. Труды семинара).
- Александр Анатольевич Иванов. Вычисление длин орбит подгруппы в транзитивной группе подстановок // Методы и программы исследования сложных систем. Труды конференции молодых ученых. — М.: ВНИИСИ, 1983. — С. 3—7.
- Ivanov A. V. On Edge But Not Vertex Transitive Regular Graphs // Combinatorial Design Theory / Ed. C. J. Colbourn and R. Mathon. — Amsterdam, New York, Oxford, Tokyo, North-Holland: Elsevier Science Publishers B.V., 1987. — Т. 149/34. — С. 273–285. — (North-Holland Mathematics studies/Annals of Discrete Mathematics). — ISBN 0-444-70328-4.
Эта страница в последний раз была отредактирована 31 января 2024 в 16:58.
Обычно почти сразу, изредка в течении часа.