En la disciplina matemática de la teoría de grafos , un grafo de rueda es un grafo formado al conectar un solo 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 1- esqueleto 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 su lugar usan W n para denotar un gráfico de rueda con n+1 vértices (n ≥ 3), que se forma al conectar un solo vértice a todos los vértices de un ciclo de longitud n . En el resto de este artículo usamos la notación anterior.
Gráfico de rueda | |
---|---|
Vértices | norte |
Bordes | 2 ( n - 1) |
Diámetro | 2 si n > 4 1 si n = 4 |
Circunferencia | 3 |
Número cromático | 4 si n es par 3 si n es impar |
Espectro | |
Propiedades | Planar auto-dual hamiltoniano |
Notación | W n |
Tabla de gráficos y parámetros |
Construcción de set-builder
Dado un conjunto de vértices de {1, 2, 3,…, v}, el conjunto de aristas del gráfico de rueda se puede representar en la notación del generador de conjuntos mediante {{1, 2}, {1, 3},…, {1 , v}, {2, 3}, {3, 4},…, {v - 1, v}, {v, 2}}. [3]
Propiedades
Los gráficos de rueda son gráficos planos y, como tales, tienen una incrustación plana única. Más específicamente, cada gráfico de rueda es un gráfico de Halin . Son auto-duales: el dual plano de cualquier gráfico de rueda es un gráfico isomorfo. Todo gráfico plano máximo, distinto de K 4 = W 4 , contiene como subgráfico W 5 o W 6 .
Siempre hay un ciclo hamiltoniano en el gráfico de la rueda y hayciclos en W n (secuencia A002061 en la OEIS ).
Para valores impares de n , W n es un gráfico perfecto con número cromático 3: los vértices del ciclo pueden recibir dos colores y el vértice central puede recibir un tercer color. Para n pares , W n tiene un 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 unidad de distancia 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 la rueda y las matroides del torbellino , ambas derivadas de los gráficos de la rueda. El k -wheel matroid es el matroid gráfico de una rueda W k + 1 , mientras que el k -whirl matroid se deriva de la k -wheel considerando el ciclo exterior de la rueda, así como todos sus árboles de expansión , para ser 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) mostraron que W 6 tiene a Ramsey el 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 , G o su complemento contiene W 6 como subgráfico, mientras que ninguno de los 17 El gráfico de Paley -vertex ni su complemento contiene una copia de K 4 .
Referencias
- ^ Weisstein, Eric W. "Gráfico de rueda" . MathWorld .
- ^ Rosen, Kenneth H. (2011). Matemáticas discretas y sus aplicaciones (7ª ed.). McGraw-Hill. pag. 655 . ISBN 978-0073383095.
- ^ Trudeau, Richard J. (1993). Introducción a la teoría de grafos (reedición ampliada y corregida. Ed.). Nueva York: Dover Pub. pag. 56. ISBN 978-0-486-67870-2. Consultado el 8 de agosto de 2012 .
- ^ Buckley, Fred; Harary, Frank (1988), "Sobre la dimensión euclidiana de una rueda", Graphs and Combinatorics , 4 (1): 23–30, doi : 10.1007 / BF01864150.
- ^ Faudree, Ralph J .; McKay, Brendan D. (1993), "Una conjetura de Erdős y el número de Ramsey r ( W 6 )" , J. Combinatorial Math. y Computación Combinatoria. , 13 : 23–31.