Граф Любляни

Граф Любляни, у теорії графів це неорієнтований двочастковий граф зі 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 вершин і граф Іофінової-Іванова на 110 вершин.[3]

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

Історія

Люблінський граф вперше опублікували 1993 року Brouwer, Dejter та Thomassen[4] як самодоповняльний підграф (тобто, ізоморфний своєму доповненню) графу Дейтера. [5]

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

Галерея

Примітки
  1. Weisstein, Eric W. Ljubljana Graph(англ.) на сайті Wolfram MathWorld.
  2. Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. «The Ljubljana Graph.» 2002. .
  3. 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.
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.