A clique-covering sufficient condition for hamiltonicity of graphs

A graph is hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is hamiltonian is known as NP-complete problem and no satisfactory characterization for hamiltonian graphs has been found. There are several necessary conditions for hamiltonicity and since the seminal work of Dirac in 1952, many sufficient conditions were found. These conditions are usually expressed in terms of node degree, connectivity, density, toughness, independent sets, regularity and forbidden subgraphs. In this article we give an extended clique decomposition condition ensuring the hamiltonicity of a large class of graphs. Then we discuss briefly the possibility of broader extensions as well as algorithmic issues.