On the Structure of Hamiltonian Graphs with Small Independence Number

A Hamiltonian path (cycle) in a graph is a path (cycle, respectively) which passes through all of its vertices. The problems of deciding the existence of a Hamiltonian cycle (path) in an input graph are well known to be NP-complete, and restricted classes of graphs which allow for their polynomial-time solutions are intensively investigated. Until very recently the complexity was open even for graphs of independence number at most 3. A so far unpublished result of Jedlickova and Kratochvil [arXiv:2309.09228] shows that for every integer k, the problems of deciding the existence of a Hamiltonian path and cycle are polynomial-time solvable in graphs of independence number bounded by k. As a companion structural result, in this paper, we determine explicit obstacles for the existence of a Hamiltonian path for small values of k, namely for graphs of independence number 2, 3, and 4. Identifying these obstacles in an input graph yields alternative polynomial-time algorithms for deciding the existence of a Hamiltonian path with no large hidden multiplicative constants.