Grafo rueda

Grafo rueda
Algunos ejemplos de grafos rueda
Vértices	n
Aristas	2(n − 1)
Diámetro	2 si n>4 1 si n=4
Cintura	3
Número cromático	3 si n es impar 4 si n es par
Propiedades	Hamiltoniano, Auto-dual, Planar
[editar datos en Wikidata]

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²-3n+3 ciclos en W_n (sucesión A002061 en OEIS).

Los 7 ciclos de un grafo rueda W4.

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₇ es el único grafo rueda que es un grafo de distancia unidad en el plano euclidiano.^[1]​

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

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

Referencias

Enlaces externos

• Grafos. Nociones básicas - Teoría de Redes. Universidad de Antioquia.

Esta página se editó por última vez el 23 oct 2019 a las 11:39.