Граф Любляны

Граф Любляны — это неориентированный двудольный граф с 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]2.

Граф Любляны является графом Леви конфигурации Любляны, конфигурации без четырёхугольников с 56 прямыми и 56 точками[2]. В этой конфигурации каждая прямая содержит в точности 3 точки, каждая точка принадлежит в точности 3 прямым и любые две прямые пересекаются максимум в одной точке.

Алгебраические свойства

Группа автоморфизмов графа Любляны является группой порядка 168. Она действует транзитивно на рёбрах, но не на вершинах — есть симметрии, переводящие любое ребро в любое другое ребро, но нет симметрии, переводящей любую вершину в любую другую вершину. Поэтому граф Любляны является полусимметричным графом, третьим по счёту кубическим полусимметричным графом после графа Грея с 54 вершинами и графа Иванова — Иофиновой с 110 вершинами[3].

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

История

Граф Любляны впервые опубликовали в 1993 году Брауэр, Деджтер и Томассен[4] как самодополнительный подграф графа Деджтера[5].

В 1972 году Брауэр уже говорил о 112-вершинном рёберно транзитивном, но не вершинно транзитивном, кубическом графе, найденном Фостером, однако не опубликованном[6]. Кондер, Малнич, Марушич и Поточник заново открыли этот 112-вершинный граф в 2002 году и назвали его графом Любляны по имени столицы Словении[2]. Они доказали, что граф был единственным 112-вершинным рёберно транзитивным, но не вершинно транзитивным, кубическим графом, а потому это тот самый граф, который нашёл Фостер.

Галерея
  • Граф Любляны является гамильтоновым и двудольным.
  • Хроматический индекс графа Любляны равен 3.
  • Альтернативный рисунок графа Любляны.
  • Граф Любляны является графом Леви этой конфигурации.

Примечания
  1. Weisstein, Eric W. Ljubljana Graph (англ.) на сайте Wolfram MathWorld.
  2. Conder, Malnič, Marušič, Pisanski, Potočnik, 2002.
  3. Conder, Malnič, Marušič, Potočnik, 2006, с. 255—294.
  4. Brouwer, Dejter, Thomassen, 1993, с. 25—29.
  5. Klin, Lauri, Ziv-Av, 2012, с. 1175–1191.
  6. Bouwer, 1972, с. 32—40.

Литература
  • Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. A census of semisymmetric cubic graphs on up to 768 vertices // Journal of Algebraic Combinatorics. — 2006. — Т. 23. — С. 255–294. — doi:10.1007/s10801-006-7397-3.
  • Brouwer A. E., Dejter I. J., Thomassen C. Highly Symmetric Subgraphs of Hypercubes // J. Algebraic Combinat.. — 1993. — Вып. 2.
  • Klin M., Lauri J., Ziv-Av M. Links between two semisymmetric graphs on 112 vertices through the lens of association schemes // Jour. Symbolic Comput.. — 2012. — Т. 7, вып. 10.
  • Bouwer I. Z. On Edge But Not Vertex Transitive Regular Graphs // J. Combin. Th. Ser. B. — 1972. — Вып. 12.
  • Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph // IMFM Preprints. — Ljubljana: Institute of Mathematics, Physics and Mechanics, 2002. — Т. 40, вып. 845.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.