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

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

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

Построение

Цветок 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 снарком не является.

Галерея

• хроматическое число цветка J5 равно 3

• хроматический индекс цветка J5 равен 4.

• Первоначальное представление цветка J5.