Grafo rueda

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Grafo rueda
Wheel graphs.svg
Algunos ejemplos de grafos rueda
Vértices n
Aristas 2(n − 1)
Diámetro 2 si n>4
1 si n=4
Cintura (girth) 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 (Wn), 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 n2-3n+3 ciclos en Wn (sucesión A002061 en OEIS).

CyclesW4.svg
Los 7 ciclos de un grafo rueda W4.

Para valores impares de n, Wn es un grafo perfecto con número cromático 3: Los vertices del ciclo pueden proporcionar dos colores, y el vértice centro proporciona un tercer color. Para valores pares de n, Wn tiene número cromático 4, y (cuando n ≥ 6) no es perfecto. W7 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 Wn es :

P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).

Referencias[editar]

  1. Buckley, Fred; Harary, Frank (1988), «On the euclidean dimension of a wheel», Graphs and Combinatorics 4 (1): 23–30, doi:10.1007/BF01864150 .

Enlaces externos[editar]