Hamiltonian Graphs And Semi Hamiltonian Graphs
Hamiltonian Graphs
Definition: A graph $G = (V(G), E(G))$ is considered Hamiltonian if and only if the graph has a cycle containing all of the vertices of the graph. |
Definition: A Hamiltonian cycle is a cycle that contains all vertices in a graph $G$. If a graph has a Hamiltonian cycle, then the graph $G$ is said to be Hamiltonian. |
For example, let's look at the following graphs (some of which were observed in earlier pages) and determine if they're Hamiltonian.
Graph Type | Graph | Hamiltonian or Not? |
---|---|---|
Complete Graph $K_5$ | Hamiltonian. Notice that a cycle can easy be formed since all vertices $x_i$ are connected to all other vertices in $V(G)$. | |
Complete Graph $K_6$ | Hamiltonian. Same case as above. | |
Complete Bipartite Graph $K_{2,3}$ | Not Hamiltonian. | |
Complete Bipartite Graph $K_{3,3}$ | Hamiltonian. Recall that a cycle of a complete bipartite graph uses the same number of vertices from vertex set $A$ and vertex set $B$. If we want to consider Hamiltonian graphs for complete bipartite graphs, then if $V(G) = A \cup B$ and $A \cap B = \varnothing$, then | A | = | B |. | |
Disconnected Graph | Not Hamiltonian. This should be rather obvious since a cycle cannot be formed containing all vertices of the graph! | |
Graphs with Leaves | Not Hamiltonian. The degree of all vertices in a cycle is $2$, but the degree of vertex $x_1$ that is considered a leaf by definition has $\deg (x_1) = 1$. Thus a cycle cannot be formed. | |
Cube Graph $Q_3$ | Hamiltonian. In fact, $Q_k$ for all $k$ is Hamiltonian. (See Gray Codes) | |
Cycle Graph $C_6$ | Hamiltonian. It should be obvious that a cycle graph in itself contains a Hamiltonian cycle. In fact, the graph is a Hamiltonian cycle. | |
Platonic Solid: Octahedron | Hamiltonian. All platonic solids are Hamiltonian. |
Determining if a Graph is Hamiltonian
Unlike determining whether or not a graph is Eulerian, determining if a graph is Hamiltonian is much more difficult. Dirac's and Ore's Theorem provide a suitable condition though.