Test: Hamiltonian Paths & Circuits - Computer Science Engineering (CSE) MCQ

All complete graph with more than two vertices are Hamiltonian.
All wheel graphs are Hamiltonian.
K_m,n is Hamiltonian only when m = n.

Total number of H.C. in a complete graph with n vertices = n !
# H.C. starting at a particular vertex
= n! / n  = (n – 1)!
Also # edge-disjoint H.C. =
: if (n - 1)!/2 is odd
0 : otherwise

Hamiltonian graph:
A Hamiltonian graph is one which contain a Hamiltonian cycle. A Hamiltonian cycle is a cycle in which each vertex is visited exactly once.
Properties of Hamiltonian graph:
(1) A graph has a Hamiltonian circuit if each vertex has degree >=3
(2) If G= (V, E) has n>=3 vertices and every vertex has degree >=n/2, then G has a Hamilton circuit
(3) If G is a graph with n vertices and n>=3, also deg(u) + deg(v) >=n, if u and v are not connected by an edge, then G has a hamiltonion circuit.
(4) E(G) = ½(n - 1)(n - 2) + 2

Concept:
Complete bipartite graph : In this graph, vertices are partitioned into two sets, such that no vertices are connected in the same set and all vertices of one set are connected to all other vertices of different set. All possible pairs of edges are considered except edges in the same set.

Explanation:
Hamiltonian circuit: In this circuit, every vertex is visited only once. It must start and end at the same vertex.
In complete bipartite graph Km, n, when m = n, then in that case, it has a Hamiltonian circuit.
Consider m = n = 3.

Hamiltonian circuit possible in this is: {1, 4, 2, 6, 3, 5, 1}

Hamiltonian graph:
A Hamiltonian graph is one which contain a Hamiltonian cycle. A Hamiltonian cycle is a cycle in which each vertex is visited exactly once.

Properties of Hamiltonian graph:
(1) A graph has a Hamiltonian circuit if each vertex has degree >=3
(2) If G= (V, E) has n>=3 vertices and every vertex has degree >=n/2, then G has a Hamilton circuit
(3) If G is a graph with n vertices and n>=3, also deg(u) + deg(v) >=n, if u and v are not connected by an edge, then G has a hamiltonion circuit.
(4) E(G) = ½(n - 1)(n - 2) + 2

The above graph has no Hamiltonian paths. That is, we cannot traverse the graph with meeting vertices exactly once.

For a graph having N vertices traverse the permutations in N! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes N iterations (i.e.) O(N! * N).

Andreas Bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of Hamiltonian cycles.

Using dynamic programming, the time taken to solve the Hamiltonian path problem is mathematically found to be O(N² 2^N).

The first ever problem to solve the Hamiltonian path was the enumerative algorithm formulated by Martello.