Wykres wiatraka - Windmill graph
| Wykres wiatraka | |
|---|---|
.svg) Wykres Windmill Wd (5,4).
| |
| Wierzchołki | (k-1) n + 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 wykres The wiatrak wykres WD ( k , n ) jest nieukierunkowane wykres skonstruowany k ≥ 2, a n ≥ 2 przez łączenie n kopii pełnego wykres K K na wspólnej uniwersalnego wierzchołka . Oznacza to, że jest to 1-klikowa suma tych pełnych wykresów.
Nieruchomości
Ma (k-1) n + 1 wierzchołków i nk (k-1) / 2 krawędzi, obwód 3 (jeśli k> 2 ), promień 1 i średnicę 2. Ma łączność wierzchołków 1, ponieważ jego środkowy wierzchołek jest punktem artykulacji ; jednakże, podobnie jak kompletne wykresy, z których jest tworzony, jest on (k-1) połączony krawędzią. Jest banalnie doskonały i jest wykresem blokowym .
Przypadki specjalne
Zgodnie z konstrukcją, graf wiatraka Wd (3, n ) jest grafem przyjaźni F n , graf wiatraka Wd (2, n ) jest grafem gwiazdowym S n, a graf wiatraka Wd (3,2) jest grafem motylkowym .
Etykietowanie i kolorowanie
Wykres wiatraka ma liczbę chromatyczną k i indeks chromatyczny n (k-1) . Jego wielomian chromatyczny można wywnioskować z wielomianu chromatycznego całego wykresu i jest równy
Wykres wiatraka Wd ( k , n ) nie jest wdzięczny, jeśli k > 5. W 1979 roku Bermond przypuszczał, że Wd (4, n ) jest wdzięczny dla wszystkich n ≥ 4. Dzięki równoważności z rodzinami doskonałej różnicy, zostało to spełniony n ≤ 1000. Bermond, Kotzig i Turgeon okazało się, że WD ( k , n ) jest wdzięku gdy K = 4, a n = 2 lub n = 3, a przy K = 5 i m = 2. wiatraka (WD 3, n ) jest wdzięczny wtedy i tylko wtedy, gdy n ≡ 0 (mod 4) lub n ≡ 1 (mod 4).
