Remove ads
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).
| 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 | |
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).
 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 vértices 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 :
Remove ads
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
Remove ads