Снарк «Квітка»

У теорії графів, снарк «Квітка» утворює нескінченне сімейство снарків, відкрите Руфусом Айзексом у 1975 році.[1]

Снарк «Квітка»
Снарк «Квітка» J3, J5 та J7.
Вершин 4n
Ребер 6n
Обхват 3 для n=3
5 для n=5
6 для n≥7
Хроматичне число 3
Хроматичний індекс 4
Властивості Снарк для n≥5
Позначення Jn з непарним n
Снарк «Квітка» J5
Снарк «Квітка» J5.
Вершин 20
Ребер 30
Обхват 5
Хроматичне число 3
Хроматичний індекс 4
Властивості Снарк
Гіпогамільтонів

Як і інші снарки, снарк «Квітка» зв'язний кубічний граф без мостів з хроматичним індексом рівним 4. Снарк «Квітка» є негамільтонованим і непланарним. Снарки «Квітка» J5 and J7 мають книжкове вкладення 3 та число черг 2.[2]

Побудова

Снарк «Квітка» Jn можна побудувати за допомогою наступного процесу:

  • Побудуємо n копій зірки з 4 вершинами. Позначимо центральні вершини кожної зірки Ai, а зовнішні вершини Bi, Ci та Di. Ми отримали незв'язні графи з 4n вершинами та 3n ребрами (Ai – Bi, Ai – Ci та Ai – Di для 1≤in).
  • Побудуємо n-цикл (B1… Bn). Це додає n ребер.
  • Нарешті побудуємо 2n-цикл (C1… CnD1… Dn). Це додає 2n ребер.

За побудовою, снарк «Квітка» Jn є кубічним графом з 4n вершинами та 6n ребрами. Для того, щоб мати необхідні властивості, значення n має бути непарним.

Особливі випадки

Назва снарк «Квітка» іноді використовується для J5, який є снарком з 20 вершинами і 30 ребрами.[3] Це один з 6 снарків з 20 вершинами (послідовність A130315 в OEIS). Снарк «Квітка» J5 є гіпогамільтоновим графом.[4]

J3 є тривіальною варіацією графу Петерсена, створеного шляхом заміни однієї з його вершин трикутником. Цей граф також відомий як граф Тітце.[5] Для того, щоб уникнути тривіальних випадків, снарки, як правило, обмежені, щоб мати обхват не менше 5. За такого обмеження, J3 не є снарком.

Галерея

Примітки

  1. Isaacs, R. «Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable.» Amer. Math. Monthly 82, 221239, 1975.
  2. Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  3. Weisstein, Eric W. Flower Snark(англ.) на сайті Wolfram MathWorld.
  4. Weisstein, Eric W. Hypohamiltonian Graph(англ.) на сайті Wolfram MathWorld.
  5. Clark, L.; Entringer, R. (1983). Smallest maximally nonhamiltonian graphs. Periodica Mathematica Hungarica 14 (1): 57–68. doi:10.1007/BF02023582..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.