Grafo rueda
# Grafo rueda

En teoría de grafos, un grafo rueda $(W_n),$ o simplemente rueda, es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).

Los grafos rueda son grafos planos, y como tales pueden ser "incrustado" en un plano. Más específicamente, todo gráfico rueda es un grafo de Halin. Son auto-duales: el dual de cualquier grafo rueda es un grafo isomórfico.

En un grafo rueda siempre hay un ciclo hamiltoniano, habiendo $n^2-3n+3$ ciclos en $W_n$ (sucesión A002061 en OEIS).

* Los 7 ciclos de un grafo rueda $W_4.$

Para valores impares de n, $W_n$ es un grafo perfecto con número cromático 3: Los vértices del ciclo pueden proporcionar dos colores, y el vértice centro proporciona un tercer color. Para valores pares de n, $W_n$ tiene número cromático 4, y (cuando n ≥ 6) no es perfecto. $W_7$ es el único grafo rueda que es un grafo de distancia unidad en el plano euclidiano.

El polinomio cromático de un grafo rueda $W_n$ es :

$P_{W_{n}}(x)=x((x-2)^{(n)}-(-1)^{n+1}(x-2)).$

