110-вершинный граф Иванова — Иофиновой

110-вершинный граф Иванова — Иофиновой — это полусимметричный кубический граф с 110 вершинами и 165 рёбрами.

110-вершинный граф Иванова — Иофиновой
Вершин 110
Рёбер 165
Радиус 7
Диаметр 7
Обхват 10
Автоморфизмы 1320 (PGL2(11))
Хроматическое число 2
Хроматический индекс 3
Свойства Полусимметричный
Двудольный
Кубический
Гамильтонов

Свойства

Иванов и Иофинова доказали в 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].

Примечания
  1. Han and Lu Affine primitive groups and Semisymmetric graphs. combinatorics.org. Дата обращения: 12 августа 2015.
  2. Weisstein, Eric Iofinova-Ivanov Graphs. Wolfram MathWorld. Wolfram. Дата обращения: 11 августа 2015.
  3. Iofinova, Ivanov, 2013, с. 470.
  4. Conder, Malnič, Marušič, Pisanski, Potočnik, 2002.
  5. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.