Снарк «Квітка»
У теорії графів, снарк «Квітка» утворює нескінченне сімейство снарків, відкрите Руфусом Айзексом[en] у 1975 році.[1]
| Снарк «Квітка» | |
|---|---|
 Снарк «Квітка» J3, J5 та J7. | |
| Вершин | 4n |
| Ребер | 6n |
| Обхват |
3 для n=3 5 для n=5 6 для n≥7 |
| Хроматичне число | 3 |
| Хроматичний індекс | 4 |
| Число черг |
2 для n=5 2 для n=7 |
| Властивості | Снарк для n≥5 |
| Позначення | Jn з непарним n |
| Снарк «Квітка» J5 | |
|---|---|
 Снарк «Квітка» J5. | |
| Вершин | 20 |
| Ребер | 30 |
| Обхват | 5 |
| Хроматичне число | 3 |
| Хроматичний індекс | 4 |
| Властивості |
Снарк Гіпогамільтонів[en] |
Як і інші снарки, снарк «Квітка» зв'язний кубічний граф без мостів з хроматичним індексом рівним 4. Снарк «Квітка» є негамільтонованим і непланарним. Снарки «Квітка» J5 and J7 мають книжкове вкладення 3 та число черг 2.[2]
Побудова ред.
Снарк «Квітка» Jn можна побудувати за допомогою наступного процесу:
- Побудуємо n копій зірки з 4 вершинами. Позначимо центральні вершини кожної зірки Ai, а зовнішні вершини Bi, Ci та Di. Ми отримали незв'язні графи з 4n вершинами та 3n ребрами (Ai – Bi, Ai – Ci та Ai – Di для 1≤i≤n).
- Побудуємо n-цикл (B1… Bn). Це додає n ребер.
- Нарешті побудуємо 2n-цикл (C1… CnD1… Dn). Це додає 2n ребер.
За побудовою, снарк «Квітка» Jn є кубічним графом з 4n вершинами та 6n ребрами. Для того, щоб мати необхідні властивості, значення n має бути непарним.
Особливі випадки ред.
Назва снарк «Квітка» іноді використовується для J5, який є снарком з 20 вершинами і 30 ребрами.[3] Це один з 6 снарків з 20 вершинами (послідовність A130315 в OEIS). Снарк «Квітка» J5 є гіпогамільтоновим графом[en].[4]
J3 є тривіальною варіацією графу Петерсена, створеного шляхом заміни однієї з його вершин трикутником. Цей граф також відомий як граф Тітце.[5] Для того, щоб уникнути тривіальних випадків, снарки, як правило, обмежені, щоб мати обхват не менше 5. За такого обмеження, J3 не є снарком.
Галерея ред.
-
Хроматичне число снарка «Квітка»J5 3. -
Хроматичний індекс снарка «Квітка» J5 4. -
Оригінальне представлення снарка «Квітка» J5.
Примітки ред.
- ↑ Isaacs, R. «Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable.» Amer. Math. Monthly 82, 221–239, 1975.
- ↑ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
- ↑ Weisstein, Eric W. Flower Snark(англ.) на сайті Wolfram MathWorld.
- ↑ Weisstein, Eric W. Hypohamiltonian Graph(англ.) на сайті Wolfram MathWorld.
- ↑ Clark, L.; Entringer, R. (1983), Smallest maximally nonhamiltonian graphs, Periodica Mathematica Hungarica, 14 (1): 57—68, doi:10.1007/BF02023582.