Mill (teorie grafů)

hrabě "Mlýn"
Vrcholy (k-1)n+1
žebra nk(k−1)/2
Poloměr jeden
Průměr 2
obvod 3 pro k > 2
Chromatické číslo k
Chromatický index n(k-1)
Označení Wd( k , n )
 Mediální soubory na Wikimedia Commons

V teorii grafů je „mlýn“ Wd( k , n ) neorientovaný graf vytvořený pro k ≥ 2 an ≥ 2 kombinací n kopií úplných grafů K k v jednom společném vrcholu. To znamená, že se jedná o 1-klikový součet těchto kompletních grafů [1] .

Vlastnosti

Graf má (k-1)n+1 vrcholů a nk(k−1)/2 hran [2] , obvod 3 (pro k > 2 ), poloměr 1 a průměr 2. Graf má vrcholovou konektivitu 1, protože jeho centrální vrchol je artikulační bod. Nicméně, stejně jako kompletní grafy, ze kterých je tvořen, je (k-1) -hranně spojen. Graf je triviálně dokonalý graf a blokový graf .

Zvláštní příležitosti

Podle konstrukce je větrný mlýn Wd(3, n ) graf přátelství F n , větrný mlýn Wd(2, n ) je hvězda S n a větrný mlýn Wd(3,2) je „motýl“ .

Označení a barvení

"Mlýnský" graf má chromatické číslo k a chromatický index n(k-1) . Jeho chromatický polynom lze získat z chromatického polynomu celého grafu a je roven

Je dokázáno, že mlýnský graf Wd( k , n ) není půvabný , pokud k > 5 [3] . V roce 1979 Bermond předpokládal, že Wd(4, n ) je elegantní pro všechna n ≥ 4 [4] . Je známo, že to platí pro n ≤ 22 [5] . Bermond, Kotzig a Turgeon dokázali, že Wd( k , n ) není půvabné pro k = 4 an = 2 nebo n = 3 a pro k = 5 an = 2 [6] . Mlýn Wd(3, n ) je elegantní právě tehdy, když n ≡ 0 (mod 4) nebo n ≡ 1 (mod 4) [7] .

Galerie

Poznámky

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

Literatura