Mill (teoria grafurilor)

Contele "Moara"
Vârfurile (k-1)n+1
coaste nk(k−1)/2
Rază unu
Diametru 2
Circumferinţă 3 pentru k > 2
Număr cromatic k
Indicele cromatic n(k-1)
Desemnare Wd( k , n )
 Fișiere media la Wikimedia Commons

În teoria grafurilor, o „moară” Wd( k , n ) este un graf nedirecționat construit pentru k ≥ 2 și n ≥ 2 prin combinarea a n copii ale graficelor complete K k la un vârf comun. Adică este suma 1-clică a acestor grafice complete [1] .

Proprietăți

Graficul are (k-1)n+1 vârfuri și nk(k−1)/2 muchii [2] , circumferința 3 (pentru k > 2 ), raza 1 și diametrul 2. Graficul are conectivitatea vârfurilor 1 deoarece vârful central este punctul de articulare. Totuși, ca și graficele complete din care este format, este (k-1) -conectat de muchii. Graficul este un grafic trivial perfect și un grafic bloc .

Ocazii speciale

Prin construcție, moara de vânt Wd(3, n ) este un grafic de prietenie F n , moara de vânt Wd(2, n ) este o stea S n , iar moara de vânt Wd(3,2) este un „fluture” .

Marcare și colorare

Graficul „morii” are numărul cromatic k și indicele cromatic n(k-1) . Polinomul său cromatic poate fi obținut din polinomul cromatic al graficului complet și este egal cu

Se dovedește că graficul morii Wd( k , n ) nu este grațios dacă k > 5 [3] . În 1979, Bermond a presupus că Wd(4, n ) este grațios pentru toate n ≥ 4 [4] . Acest lucru este cunoscut a fi adevărat pentru n ≤ 22 [5] . Bermond, Kotzig și Turgeon au demonstrat că Wd( k , n ) nu este grațios pentru k = 4 și n = 2 sau n = 3 și pentru k = 5 și n = 2 [6] . Moara Wd(3, n ) este grațioasă dacă și numai dacă n ≡ 0 (mod 4) sau n ≡ 1 (mod 4) [7] .

Galerie

Note

  1. ↑ Gallian, 2007 , p. 1-58.
  2. ^ Weisstein , Eric W. Windmill Graph  pe site- ul Wolfram MathWorld .
  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.

Literatură