В математической области теории графов граф Любляны представляет собой неориентированный двудольный граф со 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] 2 .
Граф Любляны - это граф Леви конфигурации Любляны, конфигурации без четырехугольников с 56 линиями и 56 точками. [2] В этой конфигурации каждая прямая содержит ровно 3 точки, каждая точка принадлежит ровно 3 прямым и любые две прямые пересекаются не более чем в одной точке.
Группа автоморфизмов графа Любляны - это группа порядка 168. Она действует транзитивно на ребрах графа, но не на его вершинах: существуют симметрии , переводящие каждое ребро в любое другое ребро, но не переводящие каждую вершину в любую другую вершину. Следовательно, граф Любляны является полусимметричным графом , третьим наименьшим возможным кубическим полусимметричным графом после графа Грея на 54 вершинах и графа Иофинова-Иванова на 110 вершинах . [3]
Граф Любляны был впервые опубликован в 1993 году Брауэром , Дейтером и Томассеном [4] как самодополнительный подграф графа Дейтера .[5]