Väderkvarn graf

Väderkvarns graf
Väderkvarnens graf Wd(5,4) .
Vertices	n ( k – 1) + 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 grafer och parametrar

Inom det matematiska området för grafteorin är väderkvarnens graf Wd( k , n ) en oriktad graf konstruerad för k ≥ 2 och n ≥ 2 genom att sammanfoga n kopior av hela grafen K _k vid en delad universell vertex . Det vill säga, det är en 1-klicksumma av dessa kompletta grafer.

Egenskaper

Den har n ( k – 1) + 1 hörn och nk ( k − 1)/2 kanter, omkrets 3 (om k > 2 ), radie 1 och diameter 2. Den har vertexanslutning 1 eftersom dess centrala vertex är en artikuleringspunkt ; men liksom de kompletta graferna som den är bildad av är den ( k – 1) -kantansluten. Det är trivialt perfekt och ett blockdiagram .

Speciella fall

är väderkvarnens graf Wd(3, n ) vänskapsgrafen F _n , väderkvarnens graf Wd(2, n ) är stjärngrafen S _n och väderkvarnens graf Wd(3,2) är fjärilsgrafen .

Märkning och färgläggning

Väderkvarnens graf har kromatiskt nummer k och kromatiskt index n ( k – 1) . Dess kromatiska polynom kan härledas från det kromatiska polynomet i hela grafen och är lika med

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

Väderkvarnens graf Wd( k , n ) visar sig inte vara graciös om k > 5 . 1979 har Bermond gissat att Wd(4, n ) är graciös för alla n ≥ 4 . Genom en ekvivalens med perfekta skillnadsfamiljer har detta bevisats 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 n = 2 . Väderkvarnen Wd(3, n ) är graciös om och bara om n ≡ 0 (mod 4) eller n ≡ 1 (mod 4) .

Galleri

Små väderkvarnar grafer.