Gráfico de Roda
![]()
Como definido neste trabalho, um gráfico de roda
de ordem
, às vezes simplesmente chamado de roda
(Harary 1994, p. 46; Pemmaraju e Skiena 2003, p. 248; Tutte 2005, p. 78), é um gráfico que contém um ciclo de ordem
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
pode ser definida como a união do gráfico
, onde
é o gráfico de um botão e
é o gráfico do ciclo, tornando-o um gráfico de
-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
denota o gráfico da roda em
nós.
O gráfico tetraédrico (i.e.,
) é isomórfico para
, e
é isomórfico para o gráfico tripartido completo
. Em geral, o gráfico
-roda é o esqueleto de um
– pirâmide.
é um dos dois gráficos obtidos pela remoção de duas bordas do gráfico pentatope
, sendo o outro a casa X gráfico.
Gráficos de roda são graciosos (Frucht 1979).
O gráfico de roda
tem a dimensão gráfica 2 para
(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.


O número de ciclos de gráficos no gráfico de roda
é dado por
, ou 7, 13, 21, 31, 43, 57, … (OEIS A002061) para
, 5, ….
Em um gráfico de roda, o cubo tem grau
, e outros nós têm grau 3. Os gráficos de roda são de 3.
, onde
é o gráfico completo da ordem quatro. O número cromático de
é
|
(1)
|
O gráfico da roda
tem polinomial cromático
|
(2)
|