Articles

Gráfico de Roda

Matemática Discreta > Teoria dos Gráficos > Gráficos Simples > Gráficos Cônicos >
Matemática Discreta > Teoria dos Gráficos > Gráficos Simples > Gráficos Graciosos >
Matemática Discreta > Teoria dos Gráficos > Gráficos Simples > Gráficos Integrais >

DOWNLOAD Mathematica Notebook

Como definido neste trabalho, um gráfico de roda W_n de ordem n, às vezes simplesmente chamado de roda n (Harary 1994, p. 46; Pemmaraju e Skiena 2003, p. 248; Tutte 2005, p. 78), é um gráfico que contém um ciclo de ordem n-1 e para o qual cada vértice do ciclo está ligado a um outro vértice do gráfico conhecido como o cubo. As arestas de uma roda que incluem o cubo são chamadas raios (Skiena 1990, p. 146). A roda W_n pode ser definida como a união do gráfico K_1+C_(n-1), onde K_1 é o gráfico de um botão e C_n é o gráfico do ciclo, tornando-o um gráfico de (n,1)-cone.

Note que existem duas convenções para a indexação dos gráficos de roda, com alguns autores (e.g, Gallian 2007), adoptando a convenção que W_n denota o gráfico da roda em n+1 nós.

O gráfico tetraédrico (i.e., K_4) é isomórfico para W_4, e W_5 é isomórfico para o gráfico tripartido completo K_(1,2,2). Em geral, o gráfico n-roda é o esqueleto de um (n-1)– pirâmide.

W_5 é um dos dois gráficos obtidos pela remoção de duas bordas do gráfico pentatope K_5, sendo o outro a casa X gráfico.

Gráficos de roda são graciosos (Frucht 1979).

O gráfico de roda W_n tem a dimensão gráfica 2 para n=7 (e portanto é unidade-distância) e dimensão 3 caso contrário (e portanto não unidade-distância) (Erdős et al. 1965, Buckley and Harary 1988).

Any wheel graph is a self-dual graph.

Gráficos de roda podem ser construídos na Linguagem Wolfram usando WheelGraph. As propriedades pré-calculadas de um número de gráficos de roda estão disponíveis via GraphData.

WheelGraphCycles4WheelGraphCycles5

O número de ciclos de gráficos no gráfico de roda W_n é dado por n^2-3n+3, ou 7, 13, 21, 31, 43, 57, … (OEIS A002061) para n=4, 5, ….

Em um gráfico de roda, o cubo tem grau n-1, e outros nós têm grau 3. Os gráficos de roda são de 3. W_4=K_4, onde K_4 é o gráfico completo da ordem quatro. O número cromático de W_n é

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

O gráfico da roda W_n tem polinomial cromático

 pi(x)=x.
(2)