Граф Любляны — это неориентированный двудольный граф с 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.
Альтернативный рисунок графа Любляны.
Граф Любляны является графом Леви этой конфигурации.
Читайте также
Трудовые споры: как добиться справедливости от недобросовестного работодателя
Трудовые отношения — это тонкая материя, полная нюансов и правовых
Как отличить брендовые очки от подделки
Брендовые солнцезащитные очки — это не только модный аксессуар, но
Дизайн встроенной кухни: как оптимизировать пространство
Несмотря на большое разнообразие готовой (типовой) мебели, мебель на заказ
Михаил Владимирович Мишустин: отличный управленец и экономист
Михаил Владимирович Мишустин — выдающийся российский государственный и политический деятель,
Самые популярные рецепты пиццы: идеальное сочетание ингредиентов для настоящего гурмана
Пицца – это одно из наиболее популярных блюд в мире,
Лето – это время, когда дети, закончив учебный год, уходят
Как получить гражданство Бельгии и что оно дает?
Бельгия, расположенная в сердце Европейского союза, по праву считается одним
Когда начинать готовиться к ЕГЭ и ОГЭ 2024: полезные рекомендации
Начало нового учебного года часто становится временем повышенной тревожности как
На чем можно долететь до Мальдив? Регулярный рейс или аренда частного самолета?
Путешествие на Мальдивы — это мечта многих туристов. Острова, утопающие
Зубной имплантат: преимущества выбора при протезировании
Зубной имплантат – это современная технология, предоставляющая возможность восстановить утраченный
Яйцо шоколадное Kinder сюрприз: волшебство, которое завоевало сердца детей и взрослых
Яйцо Kinder сюрприз, безусловно, является одним из наиболее популярных шоколадных
Суши и пицца: почему они так популярны в службе доставки
Службы доставки еды становятся всё популярнее среди людей, желающих насладиться
Пептидные препараты: сущность и области применения
Пептидные препараты стали одним из важнейших направлений в современной медицине