Gráfico de molino de viento

En el campo matemático de _la teoría de grafos , el grafo molino de viento Wd( k , n ) es un grafo no dirigido construido para k ≥ 2 y n ≥ 2 mediante la unión de n copias del grafo completo Kk en un vértice universal compartido . Es decir, es una suma de 1-clique de estos grafos completos. ^{[ 1 ]}

Tiene n ( k − 1) + 1 vértices y nk ( k − 1)/2 aristas, ^{[ 2 ]} circunferencia 3 (si k > 2 ), radio 1 y diámetro 2. Tiene conectividad de vértices 1 porque su vértice central es un punto de articulación; sin embargo, al igual que los grafos completos de los que se forma, es ( k − 1) -aristas-conectado. Es trivialmente perfecto y un grafo de bloques .

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

El gráfico del molino de viento tiene número cromático k e índice cromático n ( k − 1) . Su polinomio cromático se puede deducir del polinomio cromático del gráfico completo y es igual a

${\displaystyle x\prod _{i=1}^{k-1}(xi)^{n}.}$

Se ha demostrado que el grafo de molino de viento 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 ] Mediante} una equivalencia con familias de diferencias perfectas, esto se ha demostrado para n ≤ 1000. [ ^{5 ] Bermond} , Kotzig y Turgeon demostraron que Wd( k , n ) no es elegante cuando k = 4 y n = 2 o n = 3 , y cuando k = 5 y n = 2. [ ^{6 ] El} molino de viento Wd(3, n ) es elegante si y solo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4) . ^{[ 7 ]}