Hamiltonian Paths and Cycles

Hamiltonian Paths And Cycles

Recall that a path can be defined as a nonempty graph, P = (V, E), in which V = {x₀, x₁, …, x_k} and E = {x₀x₁, x₁x₂, …, x_k−1x_k}. Therefore, it concatenates vertices sequentially so that connects x₀ and x_k.

A Hamiltonian path or traceable path is one that contains every vertex of a graph exactly once. Also a Hamiltonian cycle is a cycle which includes every vertices of a graph (Bondy & Murty, 2008). Example of Hamiltonian path and Hamiltonian cycle are shown in Figure 1(a) and Figure 1(b) respectively.

Figure 1.

(a) An example of Hamiltonian path and (b) an example of Hamiltonian cycle

A traceable graph is a graph which contains a Hamiltonian path and a Hamiltonian graph is one which contains a Hamiltonian cycle (Bondy & Murty, 2008). Figure 2(a) represents the dodecahedron which is a Hamiltonian graph and Figure 2(b) represents the Hershel graph which is traceable.

Figure 2.

Hamiltonian and traceable graphs: (a) the dodecahedron and (b) the Hershel graph

Furthermore, a graph is Hamiltonian connected graph if for every pair of vertices the graph is traceable. Also a Hamiltonian decomposition is decomposition such that every subgraph contains a Hamiltonian cycle (Balakrishnan, 1995).

Hamiltonain Graph Problems

In this section, some most known traversal problems is introduced which involves finding a cycle passing through all the vertices of a graph.