WikiDer > Цветочный снарк

Flower snark
Цветочный снарк
Цветок snarks.svg
Цветок 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
Цветок snarkv.svg
Цветок Снарк 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 это не шутка.

Галерея

Рекомендации

  1. ^ Айзекс Р. (1975). «Бесконечные семейства нетривиальных трехвалентных графов, которые невозможно раскрасить». Амер. Математика. Ежемесячно. 82: 221–239. Дои:10.1080/00029890.1975.11993805. JSTOR 2319844.
  2. ^ Вольц, Джессика; Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
  3. ^ Вайсштейн, Эрик В. «Флауэр Снарк». MathWorld.
  4. ^ Вайсштейн, Эрик В. «Гипогамильтонов граф». MathWorld.
  5. ^ Clark, L .; Энтринджер Р. (1983), "Наименьшие максимально негамильтоновы графы", Periodica Mathematica Hungarica, 14 (1): 57–68, Дои:10.1007 / BF02023582.