En la disciplina matemática de la teoría de grafos , un grafo de rueda es un grafo formado al conectar un único vértice universal a todos los vértices de un ciclo . Un grafo de rueda con n vértices también se puede definir como el esqueleto 1 de una pirámide ( n – 1 )-gonal .
Algunos autores [1] escriben W n para denotar un grafo de rueda con n vértices ( n ≥ 4 ); otros autores [2] en cambio usan W n para denotar un grafo de rueda con n + 1 vértices ( n ≥ 3 ), que se forma conectando un único vértice a todos los vértices de un ciclo de longitud n . La primera notación se utiliza en el resto de este artículo y en la tabla de la derecha.
{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}} [3] sería el conjunto de aristas de un grafo de rueda con el conjunto de vértices {1, 2, …, v} en el que el vértice 1 es un vértice universal .
Los grafos de rueda son grafos planares y tienen una incrustación plana única. Más específicamente, cada grafo de rueda es un grafo de Halin . Son autoduales: el dual planar de cualquier grafo de rueda es un grafo isomorfo . Cada grafo planar maximal, excepto K 4 = W 4 , contiene como subgrafo W 5 o W 6 .
Siempre hay un ciclo hamiltoniano en el gráfico de la rueda y hay ciclos en W n (secuencia A002061 en la OEIS ).
Para valores impares de n , W n es un grafo perfecto con número cromático 3: los vértices del ciclo pueden tener dos colores y el vértice central 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 de rueda que es un grafo de distancia unitaria en el plano euclidiano. [4]
El polinomio cromático del gráfico de la rueda W n es:
En la teoría de matroides , dos clases especiales particularmente importantes de matroides son los matroides de rueda y los matroides de remolino , ambos derivados de gráficos de rueda. El matroide de rueda k es el matroide gráfico de una rueda W k+1 , mientras que el matroide de remolino k se deriva de la rueda k al considerar el ciclo externo de la rueda, así como todos sus árboles de expansión , como independientes.
La rueda W 6 proporcionó un contraejemplo a una conjetura de Paul Erdős sobre la teoría de Ramsey : había conjeturado que el grafo completo tiene el número de Ramsey más pequeño entre todos los grafos con el mismo número cromático, pero Faudree y McKay (1993) demostraron que W 6 tiene el número de Ramsey 17 mientras que el grafo completo con el mismo número cromático, K 4 , tiene el número de Ramsey 18. [5] Es decir, para cada grafo de 17 vértices G , G o su complemento contienen a W 6 como subgrafo, mientras que ni el grafo de Paley de 17 vértices ni su complemento contienen una copia de K 4 .
