Wheel Graph | SlayStudy

A wheel graph is obtained by connecting a vertex to all the vertices of a cycle graph. It is denoted by W_n, 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, W_n 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 W_n is

3 if n is odd.
4 if n is even.

Diameter of a Wheel graph W_n 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 $n^2-3n+3$ .

Proof

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 $2\; to\; n-1\; ( n-2\; ways)$ consequent vertices to the cycle. Each contribution from the outer cycle can further rotate $n-1$ times. Thus, the total number of cycles that include the Hub node = $(n-1)(n-2)$ . There is only one cycle that doesn’t include the Hub node.

Total cycles = $(n-1)(n-2) + 1 = 3n^2 - 3n + 3$

Every wheel graph contains a Hamiltonian path. The total number of an undirected Hamiltonian path in a wheel graph, W_n is $2(n-1)(n-2)$ .

Proof

First, we count the number of Hamiltonian paths who end/start with the Hub node. There are $n-1$ 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.

Hamiltonian path in wheel graph with hub as start/end node example

Total number of Hamiltonian paths with Hub as start/end = $2(n-1)$

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 $n-1$ ways. For each adjacent pair, there are $n-2$ ways to choose start/end nodes. See the following example.

Hamiltonian path in wheel graph with hub connected to non-adjacent edges example

Total number of Hamiltonian path when hub is connected to adjacent nodes = $(n-1)(n-2)$

Now, we consider the case when Hub is connected to non-adjacent nodes. We can choose 2 non-adjacent vertices in $\binom{n-1}{2} - (n-1) = \dfrac{(n-1)(n-4)}{2}$ ways. Each non-adjacent pair will correspond to 2 Hamiltonian paths – one clockwise and one anti-clockwise. See the following example.

Hamiltonian path in wheel graph with hub connected to non-adjacent nodes of the cycle example

Total Hamiltonian paths when hub is connected to non-adjacent pair of nodes = $\dfrac{(n-1)(n-4)}{2} * 2 = (n-1)(n-4)$

Total Hamiltonian Paths = $2(n-1) + (n-1)(n-2) + (n-1)(n-4) = 2(n-1)(n-4)$

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 W_n is $n-1$ .

Proof

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 $n-1$ . See the following figure for a better understanding.

Read

Properties of Wheel Graph

Leave a Comment Cancel Reply