Мичельськіан

Мичельськіа́н або граф Миче́льського неорієнтованого графа — граф, отриманий застосуванням побудови Мичельського Шаблон:Harvard citation. Побудова зберігає відсутність трикутників, але збільшує хроматичне число. Мичельський показав, що застосовуючи пробудову повторно до початкового графа без трикутників, можна отримати графи без трикутників довільно великого розміру.

Побудова

Граф Ґрьоча як мичельскіан 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 Шаблон:Harvard citation.

Багаторазове повторення побудови мичельськіана

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

Застосовуючи побудову мичельськіана повторно, починаючи від графа з єдиним ребром, отримаємо послідовність графів M_i = μ(M_i-1), іноді також званих графами Мичельського. Кілька перших графів у цій послідовності — це графи M₂ = K₂ з двома вершинами, з'єднаними ребром, цикл M₃ = C₅ і граф Ґрьоча з 11 вершинами і 20 ребрами.

У загальному випадку графи послідовності M_i не мають трикутників, (i-1)-вершинно зв'язні й i-хроматичні. M_i має $3\times 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 Шаблон:Harvard citation.
• Якщо G не має трикутників, то μ(G) теж не має трикутників Шаблон:Harvard citation.
• Узагальнюючи, якщо G має клікове число ω(G), то μ(G) має клікове число max (2, ω(G)) Шаблон:Harvard citation.
• Якщо G — фактор-критичний граф, то таким самим є μ(G) Шаблон:Harvard citation. Зокрема, кожен граф M_i для i ≥ 2 є фактор-критичним.
• Якщо G — гамільтонів цикл, то таким самим є μ(G) Шаблон:Harvard citation.
• Якщо G має число домінування γ(G), то μ(G) має домінівне число γ(G)+1 Шаблон:Harvard citation.

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

Узагальнення мичельскіана, зване конусом над графом, увів Штибіц Шаблон:Harvard citation і згодом вивчали Тардіф Шаблон:Harvard citation та Лін, Ву, Лем і Гу Шаблон:Harvard citation.

Нехай 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.

Література

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