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