Граф Любляни

Граф Любляни, у теорії графів це неорієнтований двочастковий граф зі 112 вершинами і 168 ребрами.

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

Це кубічний граф з діаметром 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].

Граф Любляни є графом Леві в конфігурації Любляни, конфігурація безчотирикутників містить 56 ліній і 56 точок. У цій конфігурації, кожна лінія містить рівно 3 точки, кожна точка належить рівно 3 лініям і будь-які дві лінії перетинаються не більше ніж в одній точці.

Алгебраїчні властивості

Група автоморфізмів графу Любляни є група порядку 168. Вона діє транзитивно на ребра графу, але не на його вершини: існують симетрії, які відображають будь-яке ребро в будь-яке інше ребро, але це не можливо для вершин. Таким чином, граф Любляни напівсиметричний граф, третій найменший можливий кубічний напівсиметричний граф після графу Грея на 54 вершин і ^[en] на 110 вершин.

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

${\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 року ^[en], ^[en] та ^[en] як самодоповняльний підграф (тобто, ізоморфний своєму доповненню) ^[en].

У 1972, Brouwer звернув увагу на граф зі 112-вершинами реберно-, але не вершинно-транзитивно кубічний граф, який знайшов Рональд Фостер, але це не було опубліковано. ^[en], Malnič, ^[en], ^[en] та Potočnik повторно знайшли цей 112-вершинний граф у 2002 році і назвали його Любляна на честь столиці Словенії. Вони довели, що це єдиний 112-вершинний граф реберно-, але не вершинно-транзитивний кубічний граф і, отже, цей граф знайшов Фостер.

Галерея

• Хроматичне число графу Любляни 2.
• Хроматичний індекс графу Любляни 3.
• Альтернативне зображення графу Любляни.
• Граф Любляни є граф Леві у цій конфігурації.
• Граф Любляни з вкладеним графом Хівуда.

Примітки

1. Weisstein, Eric W. Ljubljana Graph(англ.) на сайті Wolfram MathWorld.
2. ; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. «The Ljubljana Graph.» 2002. [1].
3. , Aleksander Malnič, Dragan Marušič and Primž Potočnik. «A census of semisymmetric cubic graphs on up to 768 vertices.» Journal of Algebraic Combinatorics: An International Journal. Volume 23, Issue 3, pages 255—294, 2006.
4. Brouwer, A. E.; Dejter, I. J.; and Thomassen, C. «Highly Symmetric Subgraphs of Hypercubes.» J. Algebraic Combinat. 2, 25-29, 1993.
5. Klin M.; Lauri J.; Ziv-Av M. «Links between two semisymmetric graphs on 112 vertices through the lens of association schemes», Jour. Symbolic Comput., 47–10, 2012, 1175—1191.
6. Bouwer, I. A. «On Edge But Not Vertex Transitive Regular Graphs.» J. Combin. Th. Ser. B 12, 32-40, 1972.