A Hamiltionian path or cycle (a.k.a. Hamiltonian circuit) is a path through a graph that visits each vertex exactly once, resp. a closed path through the graph.
hamiltonian(edges, start = 1, cycle = TRUE)Returns a vector containing vertex number of a valid path or cycle,
or NULL if no path or cycle has been found (i.e., does not exist);
If a cycle was requested, there exists an edge from the last to the first
vertex in this list of edges.
an edge list describing an undirected graph.
vertex number to start the path or cycle.
Boolean, should a path or a full cycle be found.
Hans W. Borchers
hamiltonian() applies a backtracking algorithm that is relatively
efficient for graphs of up to 30--40 vertices. The edge list is first
transformed to a list where the i-th component contains the list
of all vertices connected to vertex i.
The edge list must be of the form c(v1, v2, v3, v2, ...) meaning
that there are edges v1 --> v2, v3 --> v4, etc., connecting these
vertices. Therefore, an edge list has an even number of entries.
If the function returns NULL, there is no Hamiltonian path or
cycle. The function does not check if the graph is connected or not. And
if cycle = TRUE is used, then there also exists an edge from the
last to the first entry in the resulting path.
Ifa Hamiltonian cycle exists in the graph it will be found whatever the starting vertex was. For a Hamiltonian path this is different and a successful search may very well depend on the start.
Papadimitriou, Ch. H., and K. Steiglitz (1998). Optimization Problems: Algorithms and Complexity. Prentice-Hall/Dover Publications.
Package igraph