Граф Любляны

Граф Любляны — это неориентированный двудольный граф с 112 вершинами и 168 рёбрами.

Граф является кубическим графом с диаметром 8, радиусом 7, хроматическим числом 2 и хроматическим индексом 3. Его обхват равен 10 и в нём есть ровно 168 циклов длины 10. Есть также 168 циклов длины 12.

Построение

Граф Любляны гамильтонов и может быть построен из 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 точками. В этой конфигурации каждая прямая содержит в точности 3 точки, каждая точка принадлежит в точности 3 прямым и любые две прямые пересекаются максимум в одной точке.

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

Группа автоморфизмов графа Любляны является группой порядка 168. Она действует транзитивно на рёбрах, но не на вершинах — есть симметрии, переводящие любое ребро в любое другое ребро, но нет симметрии, переводящей любую вершину в любую другую вершину. Поэтому граф Любляны является полусимметричным графом, третьим по счёту кубическим полусимметричным графом после графа Грея с 54 вершинами и графа Иванова — Иофиновой с 110 вершинами.

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

( x − 3 ) x 14 ( x + 3 ) ( x 2 − x − 4 ) 7 ( x 2 − 2 ) 6 ( x 2 + x − 4 ) 7 ( x 4 − 6 x 2 + 4 ) 14 .   {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 году Брауэр, Деджтер и Томассен как самодополнительный подграф графа Деджтера.

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

Галерея

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

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

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

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