Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length nΩ(1/loglogn)=exp(Ω(logn/loglogn))nΩ(1/loglogn)=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if GG has a maximum degree dd and has a cycle with kk vertices (or a 3-cyclable minor HH with kk vertices), then we can find in O(n3)O(n3) time a cycle in GG of length kΩ(1/logd)kΩ(1/logd). From this we infer that if GG has a cycle of length kk, then one can find in O(n3)O(n3) time a cycle of length kΩ(1/(log(n/k)+loglogn))kΩ(1/(log(n/k)+loglogn)), which implies the result for Hamiltonian graphs. Our results improve, for some values of kk and dd, a recent result of Gabow (2004) [11] showing that if GG has a cycle of length kk, then one can find in polynomial time a cycle in GG of length exp(Ω(logk/loglogk)). We finally show that if GG has fixed Euler genus gg and has a cycle with kk vertices (or a 3-cyclable minor HH with kk vertices), then we can find in polynomial time a cycle in GG of length f(g)kΩ(1)f(g)kΩ(1), running in time O(n2)O(n2) for planar graphs.