A fast parallel algorithm for ¯nding Hamiltonian cycles in dense graphs

Suppose 0 \u3c η \u3c 1 is given. We call a graph, G, on n vertices an η-Chvatal graph if its degree sequence d1 ≤ d2 ≤ . . . ≤ dn satisfies: for k \u3c n/2, dk ≤ min{k + ηn, n/2} implies dn−k−ηn ≥ n − k. (Thus for η = 0 we get the well-known Chvatal graphs.) An N C 4-algorithm is presented which accepts as input an η-Chvatal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best N C -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs ( δ(G) ≥ n/2 where δ(G) is the minimum degree in G )