Articles

Gráfico de rueda

Matemática discreta > Teoría de grafos > Grafos simples > Grafos de cono >
Matemática discreta > Teoría de grafos > Grafos simples > Grafos Graciosos >
Matemática Discreta > Teoría de Grafos > Grafos Simples > Grafos Integrales >

Como se define en este trabajo, un gráfico de rueda W_n de orden n, a veces llamado simplemente una rueda n (Harary 1994, p. 46; Pemmaraju y Skiena 2003, p. 248; Tutte 2005, p. 78), es un grafo que contiene un ciclo de orden n-1 y para el cual cada vértice del grafo en el ciclo está conectado a otro vértice del grafo conocido como el centro. Las aristas de una rueda que incluyen el cubo se llaman radios (Skiena 1990, p. 146). La rueda W_n puede definirse como la unión de grafos K_1+C_(n-1), donde K_1 es el grafo singleton y C_n es el grafo del ciclo, lo que lo convierte en un grafo (n,1)-cono.

Nótese que hay dos convenciones para la indexación de los grafos de rueda, con algunos autores (por ejemplo, Gallian 2007), adoptando la convención de que W_n denota el gráfico de la rueda en n+1 nodos.

El gráfico tetraédrico (es decir, K_4) es isomorfo a W_4, y W_5 es isomorfo al gráfico tripartito completo K_(1,2,2). En general, el grafo n-rueda es el esqueleto de una (n-1)-pirámide.

W_5 es uno de los dos grafos que se obtienen al eliminar dos aristas del grafo pentatopo K_5, siendo el otro el grafo de la casa X.

Los grafos de rueda son graciosos (Frucht 1979).

El grafo de la rueda W_n tiene dimensión gráfica 2 para n=7 (y por lo tanto es de distancia unitaria) y dimensión 3 en caso contrario (y por lo tanto no es de distancia unitaria) (Erdős et al. 1965, Buckley y Harary 1988).

Cualquier grafo de la rueda es un grafo autodual.

Los grafos de la rueda se pueden construir en Wolfram Language utilizando WheelGraph. Las propiedades precalculadas de un número de grafos de rueda están disponibles a través de GraphData.

WheelGraphCycles4WheelGraphCycles5

El número de ciclos del grafo W_n está dado por n^2-3n+3, o 7, 13, 21, 31, 43, 57, … (OEIS A002061) para n=4, 5, ….

En un grafo de rueda, el cubo tiene grado n-1, y otros nodos tienen grado 3. Los grafos de rueda están conectados por 3. W_4=K_4, donde K_4 es el grafo completo de orden cuatro. El número cromático de W_n es

 chi(W_n)={3 for n odd; 4 for n even.
(1)

El gráfico de la rueda W_n tiene polinomio cromático

 pi(x)=x.
(2)