Väderkvarngrafik - Windmill graph
| Väderkvarn graf | |
|---|---|
.svg) Väderkvarngrafiken Wd (5,4).
| |
| Hörn | (k-1) n + 1 |
| Kanter | nk (k − 1) / 2 |
| Radie | 1 |
| Diameter | 2 |
| Omkrets | 3 om k> 2 |
| Kromatiskt nummer | k |
| Kromatiskt index | n (k-1) |
| Notation | Wd ( k , n ) |
| Tabell över diagram och parametrar | |
I matematisk området för grafteori , den väderkvarn plotta Wd ( k , n ) är en oriktad graf konstruerad för k ≥ 2 och n ≥ 2 genom att gå med n kopior av komplett graf K k vid en delad universell vertex . Det är, det är en 1-klicksumma av dessa kompletta grafer.
Egenskaper
Den har (k-1) n + 1 hörn och nk (k − 1) / 2 kanter, omkrets 3 (om k> 2 ), radie 1 och diameter 2. Den har toppunktanslutning 1 eftersom dess centrala toppunkt är en artikulationspunkt ; liksom de fullständiga graferna från vilka den är bildad är den (k-1) -kantansluten. Det är trivialt perfekt och ett blockdiagram .
Speciella fall
Genom konstruktion, väderkvarn GRAPH Wd (3, n ) är den väns graf F n , väderkvarn GRAPH Wd (2, n ) är den stjärn graf S n och väderkvarnen plotta Wd (3,2) är den fjärils grafen .
Märkning och färgning
Väderkvarngrafiken har det kromatiska antalet k och det kromatiska indexet n (k-1) . Dess kromatiska polynom kan härledas från det kromatiska polynomet i hela grafen och är lika med
Väderkvarngrafiken Wd ( k , n ) visade sig inte vara graciös om k > 5. 1979 har Bermond antagit att Wd (4, n ) är graciös för alla n ≥ 4. Genom en ekvivalens med perfekta skillnadsfamiljer har detta varit bevisat för n ≤ 1000. Bermond, Kotzig och Turgeon bevisade att Wd ( k , n ) inte är graciös när k = 4 och n = 2 eller n = 3, och när k = 5 och m = 2. Väderkvarnen Wd ( 3, n ) är graciös om och endast om n ≡ 0 (mod 4) eller n ≡ 1 (mod 4).
