Malom (gráfelmélet)

Gróf "Malom"
Csúcsok (k-1)n+1
borda nk(k−1)/2
Sugár egy
Átmérő 2
Heveder 3, ha k > 2
Kromatikus szám k
Kromatikus index n(k-1)
Kijelölés Wd( k , n )
 Médiafájlok a Wikimedia Commons oldalon

A gráfelméletben a Wd( k , n ) „malom” egy irányítatlan gráf , amelyet k ≥ 2 és n ≥ 2 esetén építettünk fel K k teljes gráfok n másolatának egy közös csúcsban való kombinálásával . Azaz ezeknek a teljes gráfoknak az 1-klikk összege [1] .

Tulajdonságok

A gráfnak (k-1)n+1 csúcsa és nk(k-1)/2 éle van [2] , kerülete 3 ( k > 2 esetén), sugara 1 és átmérője 2. A gráf csúcsösszeköthetősége 1, mert központi csúcsa az artikulációs pont. Azonban, mint a teljes gráfok, amelyekből készült, ez is (k-1) -él-összefüggésben van. A gráf egy triviálisan tökéletes gráf és egy blokkgráf .

Különleges alkalmak

Szerkezetileg a Wd(3, n ) szélmalom egy F n barátsági gráf , a Wd(2, n ) egy S n csillag , a Wd(3,2) szélmalom pedig egy „lepke” .

Jelölés és színezés

A "malom" gráfnak k kromatikus száma és n(k-1) kromatikus indexe van . Ennek kromatikus polinomja megkapható a teljes gráf kromatikus polinomjából, és egyenlő

Bebizonyosodott, hogy a Wd( k , n ) malomgráf nem kecses , ha k > 5 [3] . 1979-ben Bermond azt sejtette, hogy Wd(4, n ) minden n ≥ 4 esetén kecses [4] . Ez köztudottan igaz n ≤ 22 esetén [5] . Bermond, Kotzig és Turgeon bebizonyította, hogy Wd( k , n ) nem kecses k = 4 és n = 2 vagy n = 3, illetve k = 5 és n = 2 esetén [6] . A Wd(3, n ) malom akkor és csak akkor kecses, ha n ≡ 0 (mod 4) vagy n ≡ 1 (mod 4) [7] .

Galéria

Jegyzetek

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

Irodalom