Снарк «двойная звезда» (Vugjt «;fkwugx [fy[;g»)

Перейти к навигации Перейти к поиску
Снарк «двойная звезда»
Вершин 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].

Примечания

[править | править код]
  1. Weisstein, Eric W. Double Star Snark (англ.) на сайте Wolfram MathWorld.
  2. 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. — JSTOR 2319844.
  3. Weisstein, Eric W. Hypohamiltonian Graph (англ.) на сайте Wolfram MathWorld.
  4. Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).