Граф Любляни
Граф Любляни, у теорії графів це неорієнтований двочастковий граф зі 112 вершинами і 168 ребрами.[1]
| Граф Любляни | |
|---|---|
 Граф Любляни — гамільтонів. | |
| Вершин | 112 |
| Ребер | 168 |
| Радіус | 7 |
| Діаметр | 8 |
| Обхват | 10 |
| Автоморфізм | 168 |
| Хроматичне число | 2 |
| Хроматичний індекс | 3 |
| Властивості |
Кубічний граф напівсиметричний граф Гамільтонів граф |
Це кубічний граф з діаметром 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 вершин і граф Іофінової-Іванова[en] на 110 вершин.[3]
Характеристичний многочлен графу Любляни:
Історія ред.
Люблінський граф вперше опублікували 1993 року Brouwer[en], Dejter[en] та Thomassen[en][4] як самодоповняльний підграф (тобто, ізоморфний своєму доповненню) графу Дейтера[en]. [5]
У 1972, Brouwer звернув увагу на граф зі 112-вершинами реберно-, але не вершинно-транзитивно кубічний граф, який знайшов Рональд Фостер, але це не було опубліковано.[6] Conder[en], Malnič, Marušič[en], Pisanski[en] та Potočnik повторно знайшли цей 112-вершинний граф у 2002 році і назвали його Любляна на честь столиці Словенії.[2] Вони довели, що це єдиний 112-вершинний граф реберно-, але не вершинно-транзитивний кубічний граф і, отже, цей граф знайшов Фостер.
Галерея ред.
-
Хроматичне число графу Любляни 2. -
Хроматичний індекс графу Любляни 3. -
Альтернативне зображення графу Любляни. -
Граф Любляни є граф Леві у цій конфігурації. -
Граф Любляни з вкладеним графом Хівуда.
Примітки ред.
- ↑ Weisstein, Eric W. Ljubljana Graph(англ.) на сайті Wolfram MathWorld.
- ↑ а б в Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. «The Ljubljana Graph.» 2002. [1].
- ↑ Marston Conder, 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.
- ↑ Brouwer, A. E.; Dejter, I. J.; and Thomassen, C. «Highly Symmetric Subgraphs of Hypercubes.» J. Algebraic Combinat. 2, 25-29, 1993.
- ↑ 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.
- ↑ Bouwer, I. A. «On Edge But Not Vertex Transitive Regular Graphs.» J. Combin. Th. Ser. B 12, 32-40, 1972.