Rueda (teoría de grafos)
| Ejemplos de gráficos de ruedas | |
|---|---|
| picos | norte |
| costillas | 2( norte − 1) |
| Diámetro |
2 para n>4 1 para n =4 |
| Circunferencia | 3 |
| Número cromático | 3 para n impar , 4 para n par |
| Propiedades |
planar dual hamiltoniano |
| Designacion | Wn _ |
| Archivos multimedia en Wikimedia Commons | |
En teoría de grafos, una rueda W n es un grafo con n vértices (n ≥ 4), formado por la conexión de un solo vértice con todos los vértices del ( n -1) -ciclo . La designación numérica de las ruedas en la literatura no está bien establecida: algunos autores usan n para indicar la duración del ciclo, por lo que su W n significa el gráfico W n+1 como se define arriba [1] . Una rueda se puede definir de la misma manera que un esqueleto de 1( n -1)-pirámide de carbón .
Establecer representación
Sea dado el conjunto de vértices {1,2,3,…,v}. El conjunto de aristas de la rueda gráfica se puede representar como un conjunto {{1,2},{1,3},…,{1,v},{2,3},{3,4},…, {v-1, v},{v,2}} [2] .
Propiedades
Las ruedas son gráficas planares , y por tanto tienen un único empotramiento en el plano. Cualquier rueda es un gráfico de Halin . Son autoduales: el gráfico dual de cualquier rueda es isomorfo a la rueda misma. Cualquier gráfico plano máximo que no sea K 4 = W 4 contiene W 5 o W 6 como subgráfico .
Siempre hay un ciclo hamiltoniano en la rueda y el número de ciclos en W n es (secuencia A002061 en OEIS ).
7 ciclos en la rueda W 4 . |
Para valores impares de n , W n es un gráfico perfecto con el número cromático 3: los vértices del ciclo se pueden colorear en dos colores y el vértice central tendrá un tercer color. Incluso para n W n la rueda tiene el número cromático 4 y (para n ≥ 6) no será un gráfico perfecto. W 7 es la única rueda que es un gráfico de unidad de distancia en el plano euclidiano [3] .
El polinomio cromático de la rueda W n es:
Hay dos tipos particularmente importantes de matroides en la teoría de matroides, ruedas y vórtices , los cuales se derivan de gráficos de ruedas. La matroide de rueda k es una matroide gráficarueda W k+1 , y la matriz de vórtice k se obtiene a partir de la matriz de rueda k declarando el ciclo exterior (borde) tan independiente como sus árboles de expansión .
La rueda W 6 proporciona un contraejemplo a la conjetura de Paul Erdős en la teoría de Ramsey : conjeturó que un 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. Sin embargo, Faudree y McKay (Faudree, McKay, 1993) demostraron que para W 6 el número de Ramsey es 17, mientras que para un gráfico completo K 4 con el mismo número cromático, el número de Ramsey es 18 [4] . Por lo tanto, para cualquier gráfico G de 17 vértices , el propio G o su complemento contienen W 6 como subgráfico, mientras que ni el gráfico de Paley de 17 vértices ni su complemento contienen K 4 .
Notas
- ↑ Weisstein, Eric W. Wheel Graph en el sitio web de Wolfram MathWorld .
- ↑ Richard J. Trudeau. Introducción a la Teoría de Grafos. — Publicación corregida y ampliada. Nueva York: Dover Pub. - Pág. 56. - ISBN 978-0-486-67870-2 .
- ↑ Fred Buckley, Frank Harary. Sobre la dimensión euclidiana de una rueda // Graficas y Combinatoria. - 1988. - V. 4 , núm. 1 . — P. 23–30 . -doi : 10.1007/ BF01864150 .
- ↑ Ralph J. Faudree, Brendan D. McKay. Una conjetura de Erdős y el número de Ramsey r ( W 6 ) // J. Combinatorial Math. y computación combinatoria. - 1993. - T. 13 . — P. 23–31 .