Mill (grafteori)

Grev "Mølle"
Toppe (k-1)n+1
ribben nk(k−1)/2
Radius en
Diameter 2
Omkreds 3 for k > 2
Kromatisk tal k
Kromatisk indeks n(k-1)
Betegnelse Wd( k , n )
 Mediefiler på Wikimedia Commons

I grafteori er en "mølle" Wd( k , n ) en urettet graf bygget til k ≥ 2 og n ≥ 2 ved at kombinere n kopier af komplette grafer K k ved et fælles toppunkt. Det vil sige, at det er 1-klik summen af ​​disse komplette grafer [1] .

Egenskaber

Grafen har (k-1)n+1 toppunkter og nk(k−1)/2 kanter [2] , omkreds 3 (for k > 2 ), radius 1 og diameter 2. Grafen har toppunktsforbindelse 1, fordi dens det centrale vertex er artikulationspunktet. Men ligesom de komplette grafer, hvorfra den er dannet, er den (k-1) -kantforbundet. Grafen er en trivielt perfekt graf og en blokgraf .

Særlige lejligheder

Ved konstruktion er vindmøllen Wd(3, n ) en venskabsgraf F n , vindmøllen Wd(2, n ) er en stjerne S n , og vindmøllen Wd(3,2) er en "sommerfugl" .

Markup og farvelægning

"Mølle"-grafen har kromatisk tal k og kromatisk indeks n(k-1) . Dets kromatiske polynomium kan fås fra det kromatiske polynomium i hele grafen og er lig med

Det er bevist, at møllegrafen Wd( k , n ) ikke er yndefuld , hvis k > 5 [3] . I 1979 formodede Bermond, at Wd(4, n ) er yndefuld for alle n ≥ 4 [4] . Dette er kendt for at være sandt for n ≤ 22 [5] . Bermond, Kotzig og Turgeon beviste, at Wd( k , n ) ikke er yndefuld for k = 4 og n = 2 eller n = 3, og for k = 5 og n = 2 [6] . Møllen Wd(3, n ) er yndefuld, hvis og kun hvis n ≡ 0 (mod 4) eller n ≡ 1 (mod 4) [7] .

Galleri

Noter

  1. ↑ Gallian, 2007 , s. 1-58.
  2. ↑ Weisstein, Eric W. Windmill Graph  på Wolfram MathWorld- webstedet .
  3. ↑ Koh, Rogers, Teo, Yap, 1980 , s. 559-571.
  4. ↑ Bermond, 1979 , s. 18-37.
  5. ↑ Huang, Skiena, 1994 , s. 225-242.
  6. ↑ Bermond, Kotzig, Turgeon, 1978 , s. 135-149.
  7. ↑ Bermond, Brouwer, Germa, 1978 , s. 35-38.

Litteratur