Мичельськіа́н або граф Миче́льського неорієнтованого графа — граф, отриманий застосуванням побудови Мичельського . Побудова зберігає відсутність трикутників, але збільшує хроматичне число. Мичельський показав, що застосовуючи пробудову повторно до початкового графа без трикутників, можна отримати графи без трикутників довільно великого розміру.
Побудова
Нехай n вершин заданого графа G — це v0, v1 і т. д. Граф Мичельського μ(G) графа G містить G в як підграф і ще n+1 вершину — по вершині ui для кожної вершини vi графа G, і ще одну вершину w. Кожна вершина ui з'єднана ребром з w так, що вершини утворюють зірку K1,n. Крім того, для кожного ребра vivj графа G граф Мичельського включає два ребра — uivj і viuj.
Так, якщо G має n вершин і m ребер, μ(G) має 2n+ 1 вершин і 3m+n ребро.
Приклад Ілюстрація показує побудову Мичельського, застосовану до циклу з п'ятьма вершинами — vi для 0 ≤ i ≤ 4. Отриманий мичельськіан — це граф Ґрьоча, граф з 11 вершинами і 20 ребрами. Граф Ґрьоча є найменшим графом без трикутників із хроматичним числом 4 .
Багаторазове повторення побудови мичельськіана
Застосовуючи побудову мичельськіана повторно, починаючи від графа з єдиним ребром, отримаємо послідовність графів Mi = μ(Mi-1), іноді також званих графами Мичельського. Кілька перших графів у цій послідовності — це графи M2 = K2 з двома вершинами, з'єднаними ребром, цикл M3 = C5 і граф Ґрьоча з 11 вершинами і 20 ребрами.
У загальному випадку графи послідовності Mi не мають трикутників, (i-1)-вершинно зв'язні й i-хроматичні. Mi має вершин (). Число ребер у Mi для малих i дорівнює
0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, … ().
Властивості
Якщо G має хроматичне число k, то μ(G) має хроматичне число k + 1 . Якщо G не має трикутників, то μ(G) теж не має трикутників . Узагальнюючи, якщо G має клікове число ω(G), то μ(G) має клікове число max (2, ω(G)) . Якщо G — фактор-критичний граф, то таким самим є μ(G) . Зокрема, кожен граф Mi для i ≥ 2 є фактор-критичним. Якщо G — гамільтонів цикл, то таким самим є μ(G) . Якщо G має число домінування γ(G), то μ(G) має домінівне число γ(G)+1 .
Конус над графами Узагальнення мичельскіана, зване конусом над графом, увів Штибіц і згодом вивчали Тардіф та Лін, Ву, Лем і Гу .
Нехай G — граф із множиною вершин і множиною ребер . Нехай дано ціле число . Для графа G назвемо m-мичельськіаном граф зі множиною вершин
,
де — це i-та копія для , а множина ребер
Визначимо як граф, отриманий доданням універсальної вершини u. Очевидно, що мичельськіан — це просто .
Примітки
Література
Как цитировано у Тардифа .