Мычельскиан

Перейти к навигацииПерейти к поиску

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

Конструкция

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

Пусть 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 (Chvátal 1974).

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

Графы Мычельского M2, M3 и M4

Применяя построение мычельскиана повторно, начиная с графа с единственным ребром, получим последовательность графов Mi = μ(Mi-1), иногда также называемых графами Мычельского. Несколько первых графов в этой последовательности — это графы M2 = K2 с двумя вершинами, соединёнными ребром, цикл M3 = C5 и граф Грёча с 11 вершинами и 20 рёбрами.

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

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, … (последовательность A122695 в OEIS).

Свойства

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

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

Обобщение мычельскиана, называемое конусом над графом, введено Штибицем (Stiebitz 1985) и впоследствии изучалось Тардифом (Tardif 2001) и Лином, Ву, Лемом и Гу (Lin, Wu, Lam, Gu 2006).

Пусть G — граф с множеством вершин и множеством ребер . Пусть дано целое число . Для графа G назовём m-мычельскианом граф с множеством вершин

,

где  — это i-я копия для , а множество рёбер

Определим как граф, полученный добавлением универсальной вершины u. Очевидно, что мычельскиан — это просто [1].

Примечания

Литература

  • Václav Chvátal. Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973). — Springer-Verlag, 1974. — Т. 406. — С. 243—246. — (Lecture Notes in Mathematics).
  • Tomislav Došlić. Mycielskians and matchings // Discussiones Mathematicae Graph Theory. — 2005. — Т. 25, вып. 3.
  • David C. Fisher, Patricia A. McKenna, Elizabeth D. Boyer. Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs // Discrete Applied Mathematics. — 1998. — Т. 84, вып. 1—3. — С. 93—105. — doi:10.1016/S0166-218X(97)00126-1.
  • Wensong Lin, Jianzhuan Wu, Peter Che Bor Lam, Guohua Gu. Several parameters of generalized Mycielskians // Discrete Applied Mathematics. — 2006. — Т. 154, вып. 8. — С. 1173—1182. — doi:10.1016/j.dam.2005.11.001.
  • Jan Mycielski. Sur le coloriage des graphes // Colloq. Math.. — 1955. — Т. 3. — С. 161—162.
  • M. Stiebitz. Beiträge zur Theorie der färbungskritschen Graphen. — Habilitation thesis, Technische Universität Ilmenau, 1985. Как цитировано у Тардифа (Tardif 2001).
  • C. Tardif. Fractional chromatic numbers of cones over graphs // Journal of Graph Theory. — 2001. — Т. 38, вып. 2. — С. 87—94. — doi:10.1002/jgt.1025.
  • Weisstein, Eric W. Mycielski Graph (англ.) на сайте Wolfram MathWorld.