Hamiltonian Paths and Cycles

Hamiltonian Paths and Cycles

Mahtab Hosseininia (Amirkabir University of Technology, Iran) and Faraz Dadgostari (Université Paris 1 Panthéon-Sorbonne, France)
DOI: 10.4018/978-1-4666-2661-4.ch008

Abstract

In this chapter, the concepts of Hamiltonian paths and Hamiltonian cycles are discussed. In the first section, the history of Hamiltonian graphs is described, and then some concepts such as Hamiltonian paths, Hamiltonian cycles, traceable graphs, and Hamiltonian graphs are defined. Also some most known Hamiltonian graph problems such as travelling salesman problem (TSP), Kirkman’s cell of a bee, Icosian game, and knight’s tour problem are presented. In addition, necessary and (or) sufficient conditions for existence of a Hamiltonian cycle are investigated. Furthermore, in order to solve Hamiltonian cycle problems, some algorithms are introduced in the last section.
Chapter Preview
Top

Hamiltonian Paths And Cycles

Recall that a path can be defined as a nonempty graph, P = (V, E), in which V = {x0, x1, …, xk} and E = {x0x1, x1x2, …, xk−1xk}. Therefore, it concatenates vertices sequentially so that connects x0 and xk.

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).

Top

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.

Complete Chapter List

Search this Book:
Reset