It is known that such a cycle always exists. For n=2 such a cycle can be constructed in polynomial time.
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]
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.
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.
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.
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(n3). The expected length is known for paths and cycles and a few other classes of graphs.
Actually, Lovasz asks, does every vertex transitive graph have a Hamiltonian path?
Let v1, v2, ... , v2n be the vertices, in order, of a cycle C. If we add an arbitrary chord to C, say between vertices vi and vj, then the short chord length of this chord is the minimum distance between vi and vj in C.