Vindmølle graf - Windmill graph
| Vindmølle graf | |
|---|---|
.svg) Vindmølle-grafen Wd (5,4).
| |
| Hjørner | (k-1) n + 1 |
| Kanter | nk (k − 1) / 2 |
| Radius | 1 |
| Diameter | 2 |
| Omkreds | 3 hvis k> 2 |
| Kromatisk nummer | k |
| Kromatisk indeks | n (k-1) |
| Notation | Wd ( k , n ) |
| Tabel over grafer og parametre | |
I det matematiske felt for grafteori er vindmøllegrafen Wd ( k , n ) en ikke-rettet graf konstrueret til k ≥ 2 og n ≥ 2 ved at forbinde n kopier af den komplette graf K k ved et delt universalt toppunkt . Det vil sige, det er en 1-kliksum af disse komplette grafer.
Ejendomme
Den har (k-1) n + 1 hjørner og nk (k − 1) / 2 kanter, omkreds 3 (hvis k> 2 ), radius 1 og diameter 2. Den har toppunktforbindelse 1, fordi dens centrale toppunkt er et artikulationspunkt ; ligesom de komplette grafer, hvorfra den dannes, er den (k-1) -kantforbundet. Det er trivielt perfekt og en blokgraf .
Særlige tilfælde
Ved byggeri, vindmølle grafen Wd (3, n ) er den venskab graf F n , vindmøllen tegne Wd (2, n ) er den stjerne graf S n og vindmøllen tegne Wd (3,2) er den sommerfugl graf .
Mærkning og farvning
Vindmøllegrafen har kromatisk antal k og kromatisk indeks n (k-1) . Dets kromatiske polynom kan udledes fra det kromatiske polynom i den komplette graf og er lig med
Vindmøllegrafen Wd ( k , n ) har vist sig ikke at være yndefuld, hvis k > 5. I 1979 har Bermond formodet, at Wd (4, n ) er yndefuld for alle n ≥ 4. Gennem en ækvivalens med perfekte forskel familier, har dette været bevist for n ≤ 1000. Bermond, Kotzig og Turgeon beviste, at Wd ( k , n ) ikke er yndefuld, når k = 4 og n = 2 eller n = 3, og når k = 5 og m = 2. Vindmøllen Wd ( 3, n ) er yndefuld, hvis og kun hvis n ≡ 0 (mod 4) eller n ≡ 1 (mod 4).
