Wykres wiatraka

Wykres wiatraka
Wykres wiatraka Wd(5,4) .
Wierzchołki	n ( k – 1) + 1
Krawędzie	nk ( k - 1) / 2
Promień	1
Średnica	2
Obwód	3 jeśli k > 2
Liczba chromatyczna	k
Indeks chromatyczny	n ( k – 1)
Notacja	Wd( k , n )
Tabela wykresów i parametrów

W matematycznej dziedzinie teorii grafów graf wiatrakowy Wd( k , n ) jest grafem nieskierowanym zbudowanym dla k ≥ 2 i n ≥ 2 przez połączenie n kopii pełnego grafu K _k we wspólnym uniwersalnym wierzchołku . Oznacza to, że jest to suma 1-kliki tych pełnych wykresów.

Nieruchomości

Ma n ( k – 1) + 1 wierzchołków i nk ( k − 1)/2 krawędzi, obwód 3 (jeśli k > 2 ), promień 1 i średnicę 2. Ma spójność wierzchołków 1, ponieważ jego środkowy wierzchołek jest punktem przegubu ; jednak, podobnie jak pełne grafy, z których jest utworzony, jest ( k – 1) -spójny krawędziowo. Jest trywialnie doskonały i jest wykresem blokowym .

Przypadki specjalne

Z konstrukcji wykres wiatraka Wd(3, n ) jest wykresem przyjaźni Fn _Wd , wykres wiatraka Wd(2, n ) jest wykresem gwiazdy Sn ₍ , a wykres wiatraka 3,2) jest wykresem motyla .

Etykietowanie i kolorowanie

Wykres wiatraka ma liczbę chromatyczną k i indeks chromatyczny n ( k – 1) . Jego wielomian chromatyczny można wywnioskować z wielomianu chromatycznego pełnego wykresu i jest równy

${\ Displaystyle x \ prod _ {i = 1} ^ {k-1} (xi) ^ {n}.}$

Udowodniono, że graf wiatraka Wd( k , n ) nie jest pełen wdzięku, jeśli k > 5 . W 1979 Bermond przypuszczał, że Wd(4, n ) jest wdzięczne dla wszystkich n ≥ 4 . Udowodniono to przez równoważność z rodzinami doskonałych różnic dla n ≤ 1000 . Bermond, Kotzig i Turgeon udowodnili, że Wd( k , n ) nie jest wdzięczne, gdy k = 4 i n = 2 lub n = 3 , a gdy k = 5 i n = 2 . Wiatrak Wd(3, n ) jest wdzięczny wtedy i tylko wtedy, gdy n ≡ 0 (mod 4) lub n ≡ 1 (mod 4) .

Galeria

Małe wykresy wiatraków.