###### Hamiltonian Graphs and Semihamiltonian Graphs

Maths Applications (Year 12) - Graphs and Networks

Niamh Collie

# Hamiltonian Graphs

Letâ€™s now take a look at Hamiltonian graphs. Before we discuss this, recall briefly that in the study of networks a **path**Â refers to a walk that involves no repeat edges or vertices, and is defined as an **open** pathÂ if it starts and ends at different vertices. **Closed**Â paths, also known as **cycles**, differ in that they start and end at the same vertex.

A connected graph can be described as Hamiltonian if it contains a closed path/cycle in which every vertexÂ is visited onceÂ only (except the starting/finishing vertex). Not every edge must be included, but no edge can be travelled more than once.

Consider the network A-E above. The red arrows depict a Hamiltonian cycle ABCDE in which every vertex is visited only once (except for vertex A) and no edges are traversed more than once. Thus, this network is considered a Hamiltonian graph.

Note that there can be more than one Hamiltonian cycle in a particular graph.

# Semi-Hamiltonian Graphs

A connected graph is said to be semi-Hamiltonian if it contains an **openÂ path** that visits every vertex **once**Â only (starting and finishing at different vertices) but does not contain a Hamiltonian cycle. The same conditions regarding edges apply here in that not every edge must be included in the path, and no edge can be repeated.

Consider the network F-J above. Although a path visiting all vertices only once is possible (FGHIJ as shown by the red arrows) it is not possible to return to the starting vertex without crossing an edge twice. Thus, this network can be described as Semi-Hamiltonian.

Note that there can be more than one semi-Hamiltonian path in a particular graph.

Unlike what we have seen previously in our study of network theory regarding Eulerian graphs, there is no general test that we can use here to determine the presence of a Hamiltonian path or cycle. Often, they can only found by looking and via trial and error.

# Practical Applications

There are many ways in which we use networks in our daily lives. Letâ€™s briefly discuss one scenario in which finding a Hamiltonian path/cycle may be useful.

Consider the network above as part of a map of a new city youâ€™ve just landed in. The blue vertex labelled â€˜Hotelâ€™ is where you are staying, and the green vertices labelled K-P are all tourist attractions that you would like to see today, whilst the edges represent the roads connecting each attraction. Can you determine a route in which you are able to visit all the tourist attractions only once without repeating any edges and then finishing up back at your hotel?

The red arrows show one possible closed path/cycle from Hotel-KLMNPO-Hotel. As we have been able to determine a closed path/cycle in which each vertex is visited only once except for the starting/finishing vertex and no edges are repeated, this network is considered Hamiltonian.