Hamiltonian Graph

tutorial and example
tutorial and example

What is Hamiltonian graph?

Hamiltonian graph is a graph in which each vertex is visited exactly once. A graph that contains a Hamiltonian cycle is called a Hamiltonian graph. Sometimes it is also known as Hamilton graph.

This graph was named after the scientist William Rowan Hamilton who invented the icosian game which is also known as Hamilton’s puzzle. By using Hamilton puzzle, we have to find the Hamiltonian cycle in the edge graph of dodecahedron and he solved this problem using icosian calculus.

A graph that contains Hamiltonian path is said to be traceable. A Hamiltonian graph that has n node has graph circumference n.

Hamiltonian Path: A Hamiltonian path is the path that covers every vertices exactly once.

Hamiltonian cycle: A cycle that covers every vertices exactly once and the starting and end vertex are same is called Hamiltonian cycle.

NOTE: A Hamiltonian cycle can be converted in Hamiltonian path by removing its one edge.

Examples:

  1. A complete graph with more than two vertices is Hamiltonian.
  2. Every cycle graph is Hamiltonian.
  3. Every tournament has odd number of Hamiltonian Path.
  4. Platonic solid.
  5. Cayley graph of finite Coxeter group.

In the above figures each vertex is visited exactly once.

Properties

1. Conversion of Hamiltonian cycle to Hamiltonian path is possible by removing one of its edges, but a path can only be extended to cycle if its endpoints are adjacent.

2. All biconnected graphs are Hamiltonian.

3. A tournament is Hamiltonian if it is strongly connected.

Semi Hamiltonian Graph

The Hamiltonian graph in which each vertex is visited exactly once but the starting vertex and ending vertex are not the same then the graph is known as semi Hamiltonian graph.