Снарк Блануши
Снарк Блануши — 3-регулярный граф с 18 вершинами и 27 рёбрами[2]. Существуют два таких графа. Носят имя нашедшего оба этих графа в 1946 году югославского математика Данило Блануши[3]. (На момент 1946 года был известен всего один снарк — граф Петерсена.)
Снарки Блануши | |
---|---|
Назван в честь | Данило Блануши |
Вершин | 18 (оба) |
Рёбер | 27 (оба) |
Диаметр | 4 (оба) |
Обхват | 5 (оба) |
Автоморфизмы |
8, D4 (1-й) 4, группа Клейна (2-й) |
Хроматическое число | 3 (оба) |
Хроматический индекс | 4 (оба) |
Свойства |
снарк (оба) гипогамильтонов (оба) кубический (оба) тороидальный (только один)[1] |
Медиафайлы на Викискладе |
Как и все снарки, снарки Блануши являются связными кубическими графами без мостов с хроматическим индексом 4. Оба имеют хроматическое число 3, диаметр 4 и обхват 5. Они негамильтоновы, но гипогамильтоновы[4].
Алгебраические свойства
Группа автоморфизмов первого снарка Блануши имеет порядок 8 и изоморфна диэдрической группе — группе симметрии квадрата.
Группа автоморфизмов второго снарка Блануши является абелевой группой порядка 4 и изоморфна четверной группе Клейна — прямому произведению циклической группы на себя.
Характеристические многочлены первого и второго снарков Блануши:
- ,
- .
Обобщённые снарки Блануши
Существуют обобщения первого и второго снарков Блануши до двух бесконечных семейств снарков порядка , которые обозначаются и . Снарки Блануши являются наименьшими членами этих двух семейств[5].
В 2007 Мазак (J. Mazak) доказал, что цикловой хроматический индекс обобщённых снарков Блануши равен [6].
В 2008 Геблех (M. Ghebleh) доказал, что цикловой хроматический индекс обобщённых снарков Блануши равен [7].
Галерея
- хроматическое число первого снарка Блануши равно 3.
- хроматический индекс первого снарка Блануши равен 4.
- хроматическое число второго снарка Блануши равно 3.
- хроматический индекс второго снарка Блануши равен 4.
Примечания
- Orbanić, Alen; Pisanski, Tomaž; Randić, Milan; Servatius, Brigitte. Blanuša double // Math. Commun.. — 2004. — Т. 9, вып. 1. — С. 91–103.
- Weisstein, Eric W. Blanuša snarks (англ.) на сайте Wolfram MathWorld.
- Danilo Blanuša, «Problem cetiriju boja.» Glasnik Mat. Fiz. Astr. Ser. II. 1, 31-42, 1946.
- Eckhard Steen, «On Bicritical Snarks» Math. Slovaca, 1997.
- Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 276 and 280, 1998.
- J. Mazak, Circular chromatic index of snarks, Master’s thesis, Comenius University in Bratislava, 2007.
- M. Ghebleh, Circular Chromatic Index of Generalized Blanuša Snarks, The Electronic Journal of Combinatorics, vol 15, 2008.