| Цветочный снарк | |
|---|---|
 Цветок ловит J 3 , J 5 и J 7 . | |
| Вершины | 4 п |
| Края | 6 п |
| Обхват | 3 для n = 3 5 для n = 5 6 для n ≥ 7 |
| Хроматическое число | 3 |
| Хроматический индекс | 4 |
| Толщина книги | 3 для n = 5 3 для n = 7 |
| Номер очереди | 2 для n = 5 2 для n = 7 |
| Характеристики | Снарк для n≥5 |
| Обозначение | J n с нечетным n |
| Таблица графиков и параметров | |
| Цветок Снарк J 5 | |
|---|---|
 Цветочный снарк J 5 . | |
| Вершины | 20 |
| Края | 30 |
| Обхват | 5 |
| Хроматическое число | 3 |
| Хроматический индекс | 4 |
| Характеристики | Гипогамильтониан Снарка |
| Таблица графиков и параметров | |
В математической области теории графов , то цветок snarks образуют бесконечное семейство snarks введенного Руфуса Айзекс в 1975 г. [1]
В качестве снарков цветочные снарки являются связными кубическими графами без мостов с хроматическим индексом, равным 4. Цветочные снарки неплоские и негамильтоновы . Цветочные снарки J 5 и J 7 имеют книжную толщину 3 и номер очереди 2. [2]
Строительство [ править ]
Цветочный снарк J n может быть построен следующим образом:
- Постройте n копий звездного графа на 4 вершинах. Обозначим центральную вершину каждой звезды A i и внешние вершины B i , C i и D i . В результате получается несвязный граф на 4 n вершинах с 3 n ребрами (A i - B i , A i - C i и A i - D i для 1 ≤ i ≤ n ).
- Постройте n -цикл (B 1 ... B n ). Это добавляет n ребер.
- Наконец, построим 2n -цикл (C 1 ... C n D 1 ... D n ). Это добавляет 2n ребер.
По построению Цветочный снарк J n является кубическим графом с 4 n вершинами и 6 n ребрами. Чтобы он имел требуемые свойства, n должно быть нечетным.
Особые случаи [ править ]
Название «цветочный снарк» иногда используется для обозначения J 5 , цветочного снарка с 20 вершинами и 30 ребрами. [3] Это один из 6 снарков на 20 вершинах (последовательность A130315 в OEIS ). Цветочный снарк J 5 является гипогамильтоновым . [4]
J 3 - тривиальная вариация графа Петерсена, образованная заменой одной из его вершин треугольником. Этот граф также известен как граф Титце . [5] Во избежание тривиальных случаев снарки обычно ограничиваются обхватом не менее 5. С этим ограничением J 3 не является снарком.
Галерея [ править ]
Хроматическое число цветка СНАРКА J 5 составляет 3.
Хроматической индекс цветок СНАРКА J 5 составляет 4.
Оригинальное изображение цветка снарка J 5 .
Ссылки [ править ]
- Перейти ↑ Isaacs, R. (1975). «Бесконечные семейства нетривиальных трехвалентных графов, которые невозможно раскрасить». Амер. Математика. Ежемесячно . 82 : 221–239. DOI : 10.1080 / 00029890.1975.11993805 . JSTOR 2319844 .
- ^ Wolz, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Вайсштейн, Эрик В. "Цветочный Снарк" . MathWorld .
- ^ Вайсштейн, Эрик В. «Гипогамильтонов граф» . MathWorld .
- ^ Кларк, L .; Энтрингер Р. (1983), "Наименьшие максимально негамильтоновы графы", Periodica Mathematica Hungarica , 14 (1): 57–68, DOI : 10.1007 / BF02023582.