Мыцельскиан

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории графов мыцельскианом, или графом Мыцельского, неориентированного графа называется граф, созданный применением конструкции Мыцельского (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 — граф с множеством вершин V^0=\left\{v_1^0, v_2^0,. . ., v_n^0\right \} и множеством ребер 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 = \left \{v_j^i : v_j^0 \in V^0\right\} — это i-я копия V^0 для i = 1, 2, . . ., m, а множество рёбер

E^0 \cup \left(\bigcup^{m-1}_{i=0}\left\{v^i_j v^{i+1}_{j'}: v^0_j v^0_{j'} \in E^0\right\}\right) \cup \left\{ v^m_j u : v^m_j V^m \right \}

Определим \mu_0(G) как граф, полученный добавлением универсальной вершины u. Очевидно, что мыцельскиан — это просто \mu_1(G) [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. — В. 3. — Т. 25..
  • David C. Fisher, Patricia A. McKenna, Elizabeth D. Boyer Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs // Discrete Applied Mathematics. — 1998. — В. 1–3. — Т. 84. — С. 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. — В. 8. — Т. 154. — С. 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. — В. 2. — Т. 38. — С. 87–94. — DOI:10.1002/jgt.1025.

Внешник ссылки[править | править вики-текст]