Любляна граф
| Любляна граф | |
|---|---|
 Граф Любляны как граф-покрытие графа Хивуда | |
| Вершины | 112 |
| Края | 168 |
| Радиус | 7 |
| Диаметр | 8 |
| Обхват | 10 |
| Автоморфизмы | 168 |
| Хроматическое число | 2 |
| Хроматический индекс | 3 |
| Характеристики | Кубический Полусимметричный гамильтониан |
| Таблица графиков и параметров | |
В математической области теории графов люблянский граф — неориентированный двудольный граф со 112 вершинами и 168 ребрами , заново открытый в 2002 году и названный в честь Любляны (столицы Словении ). [1] [2]
Это кубический граф с диаметром 8, радиусом 7, хроматическим числом 2 и хроматическим индексом 3. Его обхват равен 10, и в нем ровно 168 циклов длины 10. Также имеется 168 циклов длиной 12. [1]
Строительство
[ редактировать ]Люблянский граф является гамильтоновым и может быть построен с использованием обозначений LCF : [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, - 31, -39] 2 .
Граф Любляны — это граф Леви конфигурации Любляны, конфигурация без четырехугольников с 56 линиями и 56 точками. [1] В этой конфигурации каждая линия содержит ровно 3 точки, каждая точка принадлежит ровно 3 прямым и любые две прямые пересекаются не более чем в одной точке.
Алгебраические свойства
[ редактировать ]Группа автоморфизмов люблянского графа представляет собой группу порядка 168. Она действует транзитивно на ребрах графа, но не на его вершинах: существуют симметрии, переводящие каждое ребро в любое другое ребро, но не переводящие каждую вершину в любую другую вершину. Следовательно, граф Любляны — полусимметричный граф , третий наименьший из возможных кубических полусимметричных графов после графа Грея на 54 вершинах и графа Иофиновой-Иванова на 110 вершинах . [3]
Характеристический полином люблянского графа равен
История
[ редактировать ]График Любляны был впервые опубликован в 1993 году Брауэром , Дейтером и Томассеном. [4] как самодополнительный подграф графа Дейтера . [5]
В 1972 году Бауэр уже говорил о реберном, но не вершинно-транзитивном кубическом графе со 112 вершинами, найденном Р.М. Фостером , но, тем не менее, неопубликованном. [6] Кондер , Мальнич, Марушич , Писански и Поточник заново открыли этот граф со 112 вершинами в 2002 году и назвали его графом Любляны в честь столицы Словении . [1] Они доказали, что это был уникальный ребро-, но не вершинно-транзитивный кубический граф со 112 вершинами, и, следовательно, это был граф, найденный Фостером.
Галерея
[ редактировать ]
Люблянский граф является гамильтоновым и двудольным.
Хроматический индекс люблянского графа равен 3.
Альтернативный рисунок графа Любляны.
Граф Любляны является графом Леви этой конфигурации.
Ссылки
[ редактировать ]- ^ Jump up to: а б с д Кондер, М .; Мальнич, А.; Марушич, Д.; Писански, Т.; и Поточник П. «Люблянский график». 2002. [1] .
- ^ Вайсштейн, Эрик В. «Граф Любляны» . Математический мир .
- ^ Марстон Кондер , Александр Мальнич, Драган Марушич и Примож Поточник. «Перепись полусимметричных кубических графов с числом вершин до 768». Журнал алгебраической комбинаторики: международный журнал. Том 23, выпуск 3, страницы 255–294, 2006 г.
- ^ Брауэр, А.Э.; Дейтер, Эй-Джей; и Томассен К. «Высокосимметричные подграфы гиперкубов». Ж. Алгебраический комбинат. 2, 25-29, 1993.
- ^ Клин М.; Лаури Дж.; Зив-Ав М. «Связи между двумя полусимметричными графами на 112вершины через призму ассоциативных схем», Жур. СимволическоеКомпьютер., 47–10, 2012, 1175–1191.
- ^ Бауэр, И.А. «На реберных, но не вершинно-транзитивных регулярных графах». Дж. Комбин. Т.е. Сер. Б 12, 32-40, 1972.