Любляна граф - Википедия - Ljubljana graph

Любляна график
Любляна граф - Heawood представление.jpg
Вершины112
Края168
Радиус7
Диаметр8
Обхват10
Автоморфизмы168
Хроматическое число2
Хроматический индекс3
ХарактеристикиКубический
Полусимметричный
Гамильтониан
Таблица графиков и параметров

в математический поле теория графов, то Любляна график является ненаправленный двудольный граф с 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 г. Брауэр, Дейтер и Thomassen[4]как самодополняющий подграф Граф Дейтера.[5]

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

Галерея

Рекомендации

  1. ^ Вайсштейн, Эрик В. «Любляна График». MathWorld.
  2. ^ а б c Кондер, М.; Малнич, А .; Марушич, Д .; Писанский, Т .; и Поточник П. «Люблянский график». 2002 г. [1].
  3. ^ Марстон Кондер, Александр Малнич, Драган Марушич и Примж Поточник. «Перепись полусимметричных кубических графов с числом вершин до 768». Журнал алгебраической комбинаторики: международный журнал. Том 23, выпуск 3, страницы 255-294, 2006 г.
  4. ^ Brouwer, A.E .; Дейтер, И. Дж .; и Томассен, К. "Высоко симметричные подграфы гиперкубов". J. Algebraic Combinat. 2, 25-29, 1993.
  5. ^ Клин М .; Лаури Дж .; Зив-Ав М. "Связи двух полусимметричных графов на вершинах через призму ассоциативных схем", Jour. SymbolicComput., 47–10, 2012, 1175–1191.
  6. ^ Бауэр, И. А. «О реберных, но не вершинных транзитивных регулярных графах». J. Combin. Чт. Сер. В 12, 32-40, 1972.