Снарк «двойная звезда»
| Снарк «двойная звезда» | |
|---|---|
 | |
| Вершин | 30 |
| Рёбер | 45 |
| Диаметр | 4 |
| Обхват | 6 |
| Автоморфизмы | 80 |
| Хроматическое число | 3 |
| Хроматический индекс | 4 |
| Свойства |
Снарк Гипогамильтонов |
| Книжная толщина | 3 |
| Число очередей | 2 |
Снарк «двойная звезда» — это снарк с 30 вершинами и 45 рёбрами[1].
В 1975 году Руфус Айзекс представил бесконечное семейство снарков — снарки «цветы» и BDS снарки, семейство, в которое входят два снарка Блануши, снарк Декарта и снарк Секереша (BDS — это первые буквы фамилий Blanuša, Descartes, Szekeres, то есть Блануша, Декарт, Секереша)[2]. Айзекс обнаружил также один снарк с 30 вершинами, который не принадлежит семейству BDS и не является цветком — «двойную звезду».
Как снарк, двойная звезда является связным кубическим графом без мостов с хроматическим индексом 4. Снарк «двойная звезда» не планарен и не гамильтонов, но гипогамильтонов[3]. Граф имеет книжную толщину 3 и число очередей 2[4].
Галерея
-
Хроматическое число двойной звезды равно 3.
-
Хроматический индекс двойной звезды равен 4.
Примечания
- ↑ Weisstein, Eric W. Double Star Snark (англ.) на сайте Wolfram MathWorld.
- ↑ R. Isaacs. Infinite families of non-trivial trivalent graphs which are not Tait-colorable // American Mathematical Monthly. — Mathematical Association of America, 1975. — Т. 82, вып. 3. — С. 221–239. — doi:10.2307/2319844. — .
- ↑ Weisstein, Eric W. Hypohamiltonian Graph (англ.) на сайте Wolfram MathWorld.
- ↑ Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).
 | Для улучшения этой статьи желательно: |