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