У теорії графів, снарк «Квітка» утворює нескінченне сімейство снарків, відкрите у 1975 році.Isaacs, R. «Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable.» Amer. Math. Monthly 82, 221–239, 1975.
Як і інші снарки, снарк «Квітка» зв'язний кубічний граф без мостів з хроматичним індексом рівним 4. Снарк «Квітка» є негамільтонованим і непланарним. Снарки «Квітка» J5 and J7 мають книжкове вкладення 3 та число черг 2.Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
Побудова Снарк «Квітка» 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 ребрами. Це один з 6 снарків з 20 вершинами (послідовність A130315 в OEIS). Снарк «Квітка» J5 є гіпогамільтоновим графом.
J3 є тривіальною варіацією графу Петерсена, створеного шляхом заміни однієї з його вершин трикутником. Цей граф також відомий як граф Тітце.. Для того, щоб уникнути тривіальних випадків, снарки, як правило, обмежені, щоб мати обхват не менше 5. За такого обмеження, J3 не є снарком.
Галерея
Примітки