Graf Mycielskiego

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

W teorii grafów graf Mycielskiego lub Mycielskian nieskierowanego grafu G jest to graf μ(G) stworzony dzięki konstrukcji podanej przez Jana Mycielskiego w roku 1955, pokazującej istnienie grafu, w którym największa klika ma rozmiar ≤ 2, o bezwzględnie dużej liczbie chromatycznej.

Uogólniona wersja konstrukcji została przedstawiona przez Wensonga Lin w roku 2006.

[edytuj] Konstrukcja

Graf Grötzscha jako Mycielskian 5-grafu cyklicznego

Niech n-wierzchołków grafu G będzie oznaczonych v₀, v₁, ..., v_n. Graf Mycielskiego μ(G) zawiera graf G jako izomorficzny podgraf oraz n+1 dodatkowych wierzchołków: u_i odpowiadające wierzchołkom v_i oraz wierzchołek w. Każdy wierzchołek u_i jest połączony krawędzią z wierzchołkiem w, tak, że tworzą one razem podgraf przypominający gwiazdę o n+1 wierzchołkach. Dodatkowo, dla każdej krawędzi v_iv_j w ramach konstrukcji dodawane są krawędzie u_iv_j oraz v_iu_j.

Dla grafu G o n wierzchołkach i m krawędzich powstaje graf μ(G) o 2n+1 wierzchołkach i 3m+n krawędziach.

[edytuj] Przykłady

Ilustracja przedstawia konstrukcję grafu Mycielskiego zastosowana dla grafu cyklicznego o 5 wierzchołkach. Powstały graf jest nazywany grafem Grötzscha, ma 11 wierzchołków i 20 krawędzi. Jest to najmniejszy graf w którym największa klika ma rozmiar ≤ 2 o liczbie chromatycznej równej 4.

[edytuj] Iterowane grafy Mycielskiego

Grafy Mycielskiego M₂, M₃ oraz M₄

Stosując konstrukcję Mycielskiego, zaczynając od grafu zerowego można otrzymać sekwencję M_i = μ(M_i-1), nazywaną czasami grafami Mycielskiego. Kilka pierwszych grafów otrzymanych w ten sposób to: graf zerowy, graf M₁ z jednym wierzchołkiem i bez krawędzi, graf M₂ = K₂ z dwoma wierzchołkami połączonymi krawędzią, graf M₃ = C₅ oraz graf Grötzscha z 11 wierzchołkami i 20 krawędziami.

Ogólnie, dla grafu M_i należącego do sekwencji nie istnieje klika o rozmiarze > 2, usunięcie mniej niż i-1 wierzchołków nie powoduje utraty spójności grafu, jest on także i-kolorowalny. M_i ma 3 × 2^i-2 - 1 wierzchołków (Sekwencja A083329 w OEIS). Ilość krawędzi dla grafu M_i przy początkowych wartościach i to:

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (Sekwencja A122695 w OEIS)

[edytuj] Własności

Cykl Hamiltona w grafie M₄ (graf Grötzscha)

Jeśli graf G ma liczbę chromatyczną równą k, to μ(G) ma liczbę chromatyczną równą k+1 (Mycielski 1955).
Jeśli największa klika w grafie G ma rozmiar ≤ 2, to taką samą własność ma graf μ(G) (Mycielski 1955).
Jeśli graf G posiada cykl Hamiltona, to graf μ(G) także go posiada (Fisher 1998).

[edytuj] Źródła

Na podstawie angielskiej Wikipedii:

Chvátal, Vašek (1974). "The minimality of the Mycielski graph". Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), 243–246, Berlin: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag.

Došlić, Tomislav (2005). "Mycielskians and matchings". Discuss. Math. Graph Theory 25 (3): 261–266.
Fisher, David C.; McKenna, Patricia A.; Boyer, Elizabeth D. (1998). "Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs". Discrete Applied Mathematics 84 (1–3): 93–105.

Lin, Wensong; Wu, Jianzhuan; Lam, Peter Che Bor; Gu, Guohua (2006). "Several parameters of generalized Mycielskians". Discrete Applied Mathematics 154 (8): 1173–1182.