110-вершинный граф Иофиновой–Иванова
| 110-вершинный граф Иофиновой–Иванова | |
|---|---|
 | |
| Вершины | 110 |
| Края | 165 |
| Радиус | 7 |
| Диаметр | 7 |
| Обхват | 10 |
| Автоморфизмы | 1320 (ПГЛ 2 (11)) |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Характеристики | полусимметричный двудольный кубический гамильтониан |
| Таблица графиков и параметров | |
Граф Иофиновой–Иванова со 110 вершинами — это в теории графов полусимметричный кубический граф со 110 вершинами и 165 рёбрами.
Характеристики
Иофинова и Иванов доказали в 1985 году существование пяти и только пяти полусимметричных кубических двудольных графов, группы автоморфизмов которых действуют примитивно на каждом разбиении. [1] Наименьший имеет 110 вершин. Остальные имеют 126, 182, 506 и 990. [2] 126-вершинный граф Иофиновой–Иванова также известен как 12-клетка Тутте .
Диаметр 110-вершинного графа Иофиновой–Иванова, наибольшее расстояние между любой парой вершин, равен 7. Его радиус также равен 7. Его обхват равен 10.
Он 3-связен и 3-рёберно связен: чтобы сделать его несвязным, необходимо удалить по крайней мере три ребра или по крайней мере три вершины.
Раскрашивание
Хроматическое число 110-вершинного графа Иофиной-Иванова равно 2: его вершины можно раскрасить в 2 цвета так, чтобы никакие две вершины одного цвета не были соединены ребром. Его хроматический индекс равен 3: его ребра можно раскрасить в 3 цвета так, чтобы никакие два ребра одного цвета не встречались в вершине.
Алгебраические свойства
Характеристический многочлен 110-вершинного графа Иофиной-Иванова равен . Группа симметрии 110-вершинного графа Иофиной-Иванова — это проективная линейная группа PGL 2 (11) с 1320 элементами. [3]
Полусимметрия
Немногие графы демонстрируют полусимметрию: большинство реберно-транзитивных графов также вершинно-транзитивны. Наименьший полусимметричный граф — граф Фолкмана с 20 вершинами, который является 4-регулярным. Три наименьших кубических полусимметричных графа — граф Грея с 54 вершинами, это наименьший из графов Иофины-Иванова с 110 вершинами, и граф Любляны с 112 вершинами . [4] [5] Только для пяти графов Иофины-Иванова группа симметрии действует примитивно на каждом разбиении вершин.
Ссылки
- ^ Хан и Лу. "Аффинные примитивные группы и полусимметричные графы". combinatorics.org . Получено 12 августа 2015 г.
- ^ Weisstein, Eric. "Графы Иофиновой-Иванова". Wolfram MathWorld . Wolfram . Получено 11 августа 2015 г. .
- ^ Иофинова и Иванов (2013). Исследования по алгебраической теории комбинаторных объектов. Springer. стр. 470. ISBN 9789401719728. Получено 12 августа 2015 г.
- ^ Кондер, М .; Мальнич, А.; Марушич, Д. ; Писански, Т. ; Поточник, П. (2002), «График Любляны» (PDF) , Препринты МВФМ , том. 40, нет. 845, Любляна: Институт математики, физики и механики
- ^ Кондер, Марстон ; Мальнич, Александр; Марушич, Драган ; Поточник, Примож (2006), «Перепись полусимметричных кубических графов с числом вершин до 768», Журнал алгебраической комбинаторики , 23 (3): 255–294 , doi : 10.1007/s10801-006-7397-3.
Библиография
- Иофинова, М. Е., Иванов, А. А. Бипримитивные кубические графы // Исследования по алгебраической теории комбинаторных объектов . С. 123–134, 2002. (Всесоюз. научно-исследовательский ин-т системных исследований, Москва, с. 137–152, 1985.)
- Иванов А. А. Вычисление длин орбит подгруппы в транзитивной группе подстановок // Методы исследования сложных систем . М.: ВНИИСИ, 1983. С. 3–7.
- Иванов, А. В. О рёберных, но не вершинных транзитивных регулярных графах. В комбинаторной теории проектирования (ред. К. Дж. Колборн и Р. Матон). Амстердам, Нидерланды: North-Holland, стр. 273–285, 1987.
