Любляна график - Ljubljana graph - Wikipedia

Любляна график
Граф Любляны как покрывающий граф из График Хивуда
Вершины	112
Края	168
Радиус	7
Диаметр	8
Обхват	10
Автоморфизмы	168
Хроматическое число	2
Хроматический индекс	3
Характеристики	Кубический Полусимметричный Гамильтониан
Таблица графиков и параметров

в математический поле теория графов, то Любляна график является ненаправленный двудольный граф с 112 вершины и 168 края.^[1]

Это кубический граф диаметром 8, радиусом 7, хроматическое число 2 и хроматический индекс 3. Его обхват равен 10, и в нем ровно 168 циклов длины 10. Также есть 168 циклов длиной 12.^[2]

Строительство

Граф Любляны Гамильтониан и может быть построен из Обозначение 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]².

Граф Любляны - это Граф Леви конфигурации Любляны, конфигурация без четырехугольника с 56 линиями и 56 точками.^[2] В этой конфигурации каждая линия содержит ровно 3 точки, каждая точка принадлежит ровно 3 линиям, а любые две линии пересекаются не более чем в одной точке.

Алгебраические свойства

В группа автоморфизмов графа Любляны является группой порядка 168. Она действует транзитивно на ребрах графа, но не на его вершинах: есть симметрии переводит каждое ребро в любое другое, но не переводит каждую вершину в любую другую вершину. Следовательно, граф Любляны является полусимметричный граф, третий наименьший возможный кубический полусимметричный граф после Серый график на 54 вершинах и Граф Иофиновой-Иванова на 110 вершинах.^[3]

Характеристический многочлен графа Любляны равен

${\displaystyle (x-3)x^{14}(x+3)(x^{2}-x-4)^{7}(x^{2}-2)^{6}(x^{2}+x-4)^{7}(x^{4}-6x^{2}+4)^{14}.\ }$

История

График Любляны был впервые опубликован в 1993 г. Брауэр, Дейтер и Thomassen^[4]как самодополняющий подграф Граф Дейтера.^[5]

В 1972 году Бауэр уже говорил о кубическом графе со 112 вершинами, который является реберным, но не транзитивным по вершинам. Р. М. Фостер, тем не менее, не опубликовано.^[6] Кондер, Малнич, Марушич, Писанский и Поточник переоткрыли этот 112-вершинный граф в 2002 году и назвали его Любляна график после столицы Словения.^[2] Они доказали, что это единственный кубический граф со 112 вершинами, но не транзитивный по вершинам, и поэтому именно этот граф был найден Фостером.

Галерея

• 

  Граф Любляны гамильтонов и двудольный

• 

  В хроматический индекс Люблянского графа равно 3.

• 

  Альтернативный рисунок люблянского графа.

• 

  Граф Любляны - это Граф Леви этой конфигурации.

Рекомендации

1. Вайсштейн, Эрик В. «Любляна График». MathWorld.
2. Кондер, М.; Малнич, А .; Марушич, Д .; Писанский, Т .; и Поточник П. «Люблянский график». 2002 г. [1].
3. Марстон Кондер, Александр Малнич, Драган Марушич и Примж Поточник. «Перепись полусимметричных кубических графов с числом вершин до 768». Журнал алгебраической комбинаторики: международный журнал. Том 23, выпуск 3, страницы 255-294, 2006 г.
4. Brouwer, A.E .; Дейтер, И. Дж .; и Томассен, К. "Высоко симметричные подграфы гиперкубов". J. Algebraic Combinat. 2, 25-29, 1993.
5. Клин М .; Лаури Дж .; Зив-Ав М. "Связи двух полусимметричных графов на вершинах через призму ассоциативных схем", Jour. SymbolicComput., 47–10, 2012, 1175–1191.
6. Бауэр, И. А. «О реберных, но не вершинных транзитивных регулярных графах». J. Combin. Чт. Сер. В 12, 32-40, 1972.