En la disciplina matemática de la teoría de grafos , un gráfico de rueda es un gráfico formado conectando un único vértice universal a todos los vértices de un ciclo . Un gráfico 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 gráfico de rueda con n vértices ( n ≥ 4 ); otros autores [2] en cambio usan W n para denotar un gráfico de rueda con n + 1 vértices ( n ≥ 3 ), que se forma conectando un solo vértice a todos los vértices de un ciclo de longitud n . El resto de este artículo utiliza la notación anterior.
Dado un conjunto de vértices de {1, 2, 3,…, v}, el conjunto de aristas del gráfico de rueda se puede representar en notación de generador de conjuntos mediante {{1, 2}, {1, 3},…, {1 , v}, {2, 3}, {3, 4},…, {v − 1, v}, {v, 2}}. [3]
Los gráficos de rueda son gráficos planos y tienen una incrustación plana única. Más específicamente, cada gráfico de rueda es un gráfico de Halin . Son autoduales: el dual plano de cualquier gráfico de rueda es un gráfico isomórfico . Cada gráfico plano máximo, distinto de K 4 = W 4 , contiene como subgrafo W 5 o W 6 .
Siempre hay un ciclo hamiltoniano en el gráfico de rueda y hay ciclos en W n (secuencia A002061 en el OEIS ).
Para valores impares de n , W n es un gráfico perfecto con número cromático 3: a los vértices del ciclo se les pueden dar dos colores y al vértice central un tercer color. Incluso para n , W n tiene número cromático 4 y (cuando n ≥ 6) no es perfecto. W 7 es el único gráfico de rueda que es un gráfico de distancia unitaria en el plano euclidiano. [4]
El polinomio cromático del gráfico de rueda W n es:
En la teoría de las matroides , dos clases especiales de matroides particularmente importantes son las matroides de rueda y las matroides de giro , ambas derivadas de gráficos de rueda. La matroide k -wheel es la matroide gráfica de una rueda W k+1 , mientras que la matroide k -whirl se deriva de la k -wheel al considerar el ciclo externo de la rueda, así como todos sus árboles de expansión , como independiente.
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 gráfico completo tiene el número de Ramsey más pequeño entre todos los gráficos con el mismo número cromático, pero Faudree y McKay (1993) demostraron que W 6 tiene Ramsey. número 17 mientras que el gráfico completo con el mismo número cromático, K 4 , tiene el número de Ramsey 18. [5] Es decir, para cada gráfico de 17 vértices G , ya sea G o su complemento contiene W 6 como subgrafo, mientras que ninguno de los 17 -El gráfico de Paley de vértice ni su complemento contienen una copia de K 4 .
