Снарк «Цветок»

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Снарки «Цветок» J3, J5 и J7.
Вершин 4n
Рёбер 6n
Обхват 3 для n=3
5 для n=5
6 для n≥7
Хроматическое число 3
Хроматический индекс 4
Свойства снарк для n≥5
Снарк «Цветок» J5
Вершин 20
Рёбер 30
Обхват 5
Хроматическое число 3
Хроматический индекс 4
Свойства снарк
гипогамильтонов

В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году[1].

Как и все снарки, цветы являются связными кубическими графами без мостов с хроматическим индексом 4. Они не планарны и не гамильтоновы.

Построение

Цветок 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 рёбрами[2]. Это один из 6 снарков с 20 вершинами (последовательность A130315 в OEIS). Цветок J5 является гипогамильтоновым[3].

J3 является тривиальным вариантом графа Петерсена, полученный путём применения преобразования треугольник-звезда к графу Петерсена, а затем заменой одной из вершин треугольником. Этот граф известен также как граф Титце[4]. Чтобы избежать тривиальных случаев, обычно графы с обхватом меньше 5 не рассматриваются как снарки. Если следовать этим ограничениям, J3 снарком не является.

Галерея

Примечания

  1. Isaacs R. Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable // Amer. Math : Monthly. — 1975. — Т. 82. — С. 221–239.
  2. Weisstein, Eric W. Flower Snark (англ.) на сайте Wolfram MathWorld.
  3. Weisstein, Eric W. Hypohamiltonian Graph (англ.) на сайте Wolfram MathWorld.
  4. L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14, вып. 1. — С. 57—68. — doi:10.1007/BF02023582.