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