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