Wheel Graph

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.

wheel graph

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.
wheel graph chromatic number example

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.

wheel graph is self dual example

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.

wheel graph is halin graph example

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

cycles in wheel graph W4

Every wheel graph contains a Hamiltonian path. The total number of an undirected Hamiltonian path in a wheel graph, Wn 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 Wn 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.

Hamiltonian cycle in a wheel graph

Read

Leave a Comment

Your email address will not be published. Required fields are marked *