Molino (teoría de grafos)

Cuenta "Molino"
picos (k-1)n+1
costillas nk(k−1)/2
Radio una
Diámetro 2
Circunferencia 3 para k > 2
Número cromático k
índice cromático n(k-1)
Designacion Wd( k , n )
 Archivos multimedia en Wikimedia Commons

En teoría de grafos, un “molino” Wd( k , n ) es un gráfico no dirigido construido para k ≥ 2 y n ≥ 2 mediante la combinación de n copias de gráficos completos K k en un vértice común. Es decir, es la suma de 1 camarilla de estos gráficos completos [1] .

Propiedades

El gráfico tiene (k-1)n+1 vértices y nk(k−1)/2 aristas [2] , circunferencia 3 (para k > 2 ), radio 1 y diámetro 2. El gráfico tiene conectividad de vértice 1 porque su el vértice central es el punto de articulación. Sin embargo, al igual que los gráficos completos a partir de los cuales se forma, es (k-1) -conexo por aristas. El gráfico es un gráfico trivialmente perfecto y un gráfico de bloques .

Ocasiones especiales

Por construcción, el molino de viento Wd(3, n ) es un grafo de amistad F n , el molino de viento Wd(2, n ) es una estrella S n , y el molino de viento Wd(3,2) es una “mariposa” .

Marcado y coloreado

El gráfico "molino" tiene un número cromático k y un índice cromático n(k-1) . Su polinomio cromático se puede obtener del polinomio cromático del gráfico completo y es igual a

Se demuestra que el gráfico de molino Wd( k , n ) no es elegante si k > 5 [3] . En 1979 Bermond conjeturó que Wd(4, n ) es elegante para todo n ≥ 4 [4] . Se sabe que esto es cierto para n ≤ 22 [5] . Bermond, Kotzig y Turgeon probaron que Wd( k , n ) no es elegante para k = 4 y n = 2 o n = 3, y para k = 5 y n = 2 [6] . El molino Wd(3, n ) es elegante si y solo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4) [7] .

Galería

Notas

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

Literatura