A wheel graph is obtained by connecting a vertex to all the vertices of a cycle graph. It is denoted by Wn, for n > 3 where n is the number of vertices in the graph. A wheel graph of n vertices contains a cycle graph of order n – 1 and all the vertices of the cycle are connected to a single vertex ( known as the Hub ).
The number of edges in a Wheel graph, Wn is 2n – 2.
Properties of Wheel Graph
As you can see from the examples, a wheel graph is always planar.
The chromatic number of Wheel graph Wn is
- 3 if n is odd.
- 4 if n is even.
Diameter of a Wheel graph Wn is
- 1 if n == 4
- 2 if n > 4
The wheel graph is self-dual. It means if we dual a wheel graph, then we obtain the same graph. A dual graph is obtained by assigning a vertex to each region of the graph and joining the vertices in the adjacent regions.
A Wheel graph doesn’t contain an Euler path/circuit. The simplest explanation is no wheel graph can contain exactly 0 or 2 odd degree edges.
Every Wheel graph is graceful. You can read about graceful labelling of Wheel graph here.
Every wheel graph is a Halin Graph. A Halin graph is a planar graph that is constructed by connecting the leaf nodes of a tree graph into a cycle. Suppose we have a tree with n-nodes such that there are n – 1 leaf nodes in the tree. If we join all the leaf nodes of such a tree in a cycle, we get a wheel graph.
The total number of cycles in a wheel graph is .
First, we consider those cycles that include the Hub node. All the nodes that form a cycle with the hub must be consequent to each other. The outer cycle can contribute consequent vertices to the cycle. Each contribution from the outer cycle can further rotate times. Thus, the total number of cycles that include the Hub node = . There is only one cycle that doesn’t include the Hub node.
Total cycles =
Every wheel graph contains a Hamiltonian path. The total number of an undirected Hamiltonian path in a wheel graph, Wn is .
First, we count the number of Hamiltonian paths who end/start with the Hub node. There are ways the hub can be connected to a node. Each connection corresponds to 2 Hamiltonian paths – one clockwise and one anti-clockwise. See the below image.
Total number of Hamiltonian paths with Hub as start/end =
Now, we will consider the Hamiltonian paths where the hub node is in the middle of the path. We have 2 cases.
First, we consider the case when the hub is connected to adjacent nodes. We can connect the hub node to the adjacent pair of nodes in ways. For each adjacent pair, there are ways to choose start/end nodes. See the following example.
Total number of Hamiltonian path when hub is connected to adjacent nodes =
Now, we consider the case when Hub is connected to non-adjacent nodes. We can choose 2 non-adjacent vertices in ways. Each non-adjacent pair will correspond to 2 Hamiltonian paths – one clockwise and one anti-clockwise. See the following example.
Total Hamiltonian paths when hub is connected to non-adjacent pair of nodes =
Total Hamiltonian Paths =
Note: In the above proof, the paths are undirected. It means that a path 1-2-3 is equivalent to 3-2-1. To get the number of directed paths, just multiply the equation by 2.
Every Wheel graph is also a Hamiltonian graph, that is it contains a Hamiltonian cycle. The total number of Hamiltonian cycles in a wheel graph Wn is .
The hub node of the wheel graph should be connected to adjacent nodes to form a Hamiltonian cycle. If the hub is connected to non-adjacent nodes then it’s impossible to traverse all nodes without revisiting a node. Therefore, the number of Hamiltonian cycles is equal to the number of ways to connect the hub node to the adjacent nodes, which is equal to . See the following figure for a better understanding.