Мычельскиан

Мычельскиан или граф Мычельского неориентированного графа — граф, созданный применением конструкции Мычельского Шаблон:Harv. Конструкция сохраняет отсутствие треугольников, но увеличивает хроматическое число. Мычельский показал, что повторяя конструкцию повторно к начальному графу без треугольников, можно получить графы без треугольников произвольно большого размера.

Конструкция

Граф Грёча как мычельскиан 5-циклового графа.

Пусть n вершин заданного графа G — это v₀, v₁ и так далее. Граф Мычельского μ(G) графа G содержит G в качестве подграфа и ещё n+1 вершин — по вершине u_i для каждой вершины v_i графа G, и ещё одна вершина w. Каждая вершина u_i соединена ребром с w так, что вершины образуют звезду K_1,n. Кроме того, для каждого ребра v_iv_j графа G граф Мычельского включает два ребра — u_iv_j и v_iu_j.

Так, если G имеет n вершин и m рёбер, μ(G) имеет 2n+1 вершин и 3m+n рёбер.

Пример

Иллюстрация показывает конструкции Мычельского, применённого к циклу с пятью вершинами — v_i для 0 ≤ i ≤ 4. Полученный мычельскиан — это граф Грёча, граф с 11 вершинами и 20 рёбрами. Граф Грёча является наименьшим графом без треугольников с хроматическим числом 4 Шаблон:Harv.

Многократное повторение конструкции мычельскиана

Графы Мычельского M₂, M₃ и M₄

Применяя построение мычельскиана повторно, начиная с графа с единственным ребром, получим последовательность графов M_i = μ(M_i-1), иногда также называемых графами Мычельского. Несколько первых графов в этой последовательности — это графы M₂ = K₂ с двумя вершинами, соединёнными ребром, цикл M₃ = C₅ и граф Грёча с 11 вершинами и 20 рёбрами.

В общем случае графы M_i в последовательности не имеют треугольников, (i-1)-вершинно связны и i-хроматические. M_i имеет 3 × 2^i-2 — 1 вершин (Шаблон:OEIS). Число рёбер в M_i для малых i равно

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, … (Шаблон:OEIS).

Свойства

Гамильтонов цикл в M₄ (граф Грёча)

• Если G имеет хроматическое число k, то μ(G) имеет хроматическое k + 1 Шаблон:Harv.
• Если G не имеет треугольников, то μ(G) не имеет треугольников тоже Шаблон:Harv.
• Обобщая, если G имеет кликовое число ω(G), то μ(G) имеет кликовое число max(2,ω(G)) Шаблон:Harv.
• Если G — фактор-критический граф, то таким же является μ(G) Шаблон:Harv. В частности, каждый граф M_i для i ≥ 2 является фактор-критическим.
• Если G — гамильтонов цикл, то таким же является μ(G) Шаблон:Harv.
• Если G имеет Шаблон:Не переведено 5 γ(G), то μ(G) имеет доминирующее число γ(G)+1 Шаблон:Harv.

Конус над графами

Обобщение мычельскиана, называемое конусом над графом, введено Штибицем Шаблон:Harv и впоследствии изучалось Тардифом Шаблон:Harv и Лином, Ву, Лемом и Гу Шаблон:Harv.

Пусть G — граф с множеством вершин $V^0=\{v_1^0,v_2^0,...,v_n^0\}$ и множеством ребер $E^0$. Пусть дано целое число $m\ge 1$. Для графа G назовём m-мычельскианом граф ${\mu }_m(G)$ с множеством вершин

$V^0\cup V^1\cup V^2\cup ...\cup V^m\cup \left\{u\right\}$,

где $V^i=\{v_j^i:v_j^0\in V^0\}$ — это i-я копия $V^0$ для $i=1,2,...,m$, а множество рёбер

$E^0\cup \left(\bigcup _{i=0}^{m-1}\{v_j^i{v}_{j^{\prime }}^{i+1}:v_j^0{v}_{j^{\prime }}^0\in E^0\}\right)\cup \{v_j^{m}u:v_j^m{V}^m\}$

Определим ${\mu }_0(G)$ как граф, полученный добавлением универсальной вершины u. Очевидно, что мычельскиан — это просто ${\mu }_1(G)$Шаблон:Sfn.

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга Как цитировано у Тардифа Шаблон:Harv.
• Шаблон:Статья
• Шаблон:Mathworld