INSTANCE: An n-connected graph G = (V,E), a set S of n>2 vertices.

QUESTION: Can you construct in polynomial time a cycle containing all of the vertices in S?

It is known that such a cycle always exists. For n=2 such a cycle can be constructed in polynomial time.

INSTANCE: An edge-weighted, complete M x N grid graph G = (V,E), and a positive integer K.

QUESTION: Does there exist a Hamiltonian cycle in G of weight <= K?

INSTANCE: A graph G = (V,E) with n vertices and >= 3n-5 edges.

QUESTION: Does G contain two disjoint cycles?

The answer to this question is always, yes, due to a theorem of Posa. My question is: can you find two disjoint cycles in such a graph in polynomial time? [L. Posa, On the circuits of finite graphs, Magyar Tud. Akad. Mat. Kutato Int. Kozl., 8 (1963), 355-361]

INSTANCE: A random, cubic graph G = (V,E).

QUESTION: Does G contain a Hamiltonian cycle?

Robinson and Wormald have proved that almost all random, cubic graphs are Hamiltonian. My question is: given a random, cubic graph can you find such a Hamiltonian cycle in polynomial time? Bollobas, when asked about the difficulty of computing a typical optimization parameter of a random graph, speculated that most, if not all, NP-complete problems have linear solutions when restricted to random graphs. Thus, using the Bollobas 'thesis', it should be easy to find a Hamiltonian cycle in a random, cubic graph.

INSTANCE: A Cayley graph G = (V,E).

QUESTION: Does G contain a Hamiltonian cycle?

A Cayley graph G(X) is obtained from an arbitrary group G and a finite set X of generators for G. The vertices of G(X) correspond 1-1 with the vertices of G, and two vertices u and v are adjacent in G(X) if and only if the equation ux = v holds for some generator x in X. It has long been conjectured that every Cayley graph is Hamiltonian.

INSTANCE: A 4-regular prism graph G = (V,E).

QUESTION: Does G contain a Hamiltonian cycle?

Let G be an arbitrary cubic graph and let G' be a copy of G. The prism graph on G is formed by adding edges between each vertex v in G and its isomorphic copy v' in G'. According to Rosenfeld it is not known whether every such 4-regular prism graph is Hamiltonian.

INSTANCE: A rooted tree T = (V,E,r) with |V| = n vertices.

QUESTION: What is the expected length of a random Hamiltonian walk in T, starting at the root r?

The object here is to start a random walk at vertex r and keep walking until all vertices have been visited at least once (it isn't necessary to return to the starting vertex). Having arrived at a given vertex v, the next vertex visited is chosen among its neighbors with equal probability. Wilf says that the expected length of such a walk is no greater than O(n³). The expected length is known for paths and cycles and a few other classes of graphs.

INSTANCE: An edge-weighted complete graph G = (V,E),

QUESTION: How difficult is it to find a Hamiltonian circuit whose weight cannot be lowered by an exchange of a pair of edges?

INSTANCE: A vertex transitive graph G = (V,E).

QUESTION: Does G have a Hamiltonian path?

Actually, Lovasz asks, does every vertex transitive graph have a Hamiltonian path?

INSTANCE: A graph G = (V,E) which is bridgeless.

QUESTION: Does there exist a family C of cycles of G (not necessarily distinct) such that each edge of G appears in exactly two cycles of C?

INSTANCE: A set of n positive integers {l1, l2, ... , ln}, such that each li >= 3.

QUESTION: Does there exist a Hamiltonian cubic graph G on 2n vertices whose short chord lengths are {l1,l2,...,ln}?

Let v₁, v₂, ... , v_2n be the vertices, in order, of a cycle C. If we add an arbitrary chord to C, say between vertices v_i and v_j, then the short chord length of this chord is the minimum distance between v_i and v_j in C.

INSTANCE: An n-tuple A[1..n] of 0's and 1's.

QUESTION: Does there exist a graph G = (V,E) with n vertices such that G has a cycle of length i, 3 <= i <= n if and only if A(i) = 1 {we assume that A[1] = A[2] = 0}.