As defined in this work, a wheel graph of order , sometimes simply called an -wheel (Harary 1994, p. 46; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 78), is a graph that contains a cycle of order and for which every graph vertex in the cycle is connected to one other graph vertex known as the hub. The edges of a wheel which include the hub are called spokes (Skiena 1990, p. 146). The wheel can be defined as the graph join , where is the singleton graph and is the cycle graph, making it a -cone graph. Wheel graphs of order 4 to 8 are illustrated above in a number of embeddings.
Note that some authors (e.g., Gallian 2007) adopt an alternate convention in which denotes the wheel graph on nodes.
The tetrahedral graph (i.e., ) is isomorphic to , and is isomorphic to the complete tripartite graph . In general, the -wheel graph is the skeleton of an -pyramid.
The wheel graph is isomorphic to the Jahangir graph .
is one of the two graphs obtained by removing two edges from the pentatope graph , the other being the house X graph.
is a quasi-regular graph.
Wheel graphs are graceful (Frucht 1979).
The wheel graph has graph dimension 2 for (and hence is unit-distance) and dimension 3 otherwise (and hence not unit-distance) (Erdős et al. 1965, Buckley and Harary 1988).
Wheel graphs are self-dual and pancyclic.
Wheel graphs can be constructed in the Wolfram Language using WheelGraph[n]. Precomputed properties of a number of wheel graphs are available via GraphData["Wheel", n].
The number of graph cycles in the wheel graph is given by , or 7, 13, 21, 31, 43, 57, ... (OEIS A002061) for , 5, ....
In a wheel graph, the hub has degree , and other nodes have degree 3. Wheel graphs are 3-connected. , where is the complete graph of order four. The chromatic number of is
(1)
|
The wheel graph has chromatic polynomial
(2)
|