Powers of Hamiltonian cycles in mu-inseparable graphs

Abstract

We consider sufficient conditions for the existence of k-th powers of Hamiltonian cycles in n-vertex graphs G with minimum degree mu*n for arbitrarily small mu>0. About 20 years ago Komlós, Sárközy, and Szemerédi resolved the conjectures of Pósa and Seymour and obtained optimal minimum degree conditions for this problem by showing that mu=k/(k+1) suffices for large n. Consequently, for smaller values of mu the given graph G must satisfy additional assumptions. We show that inducing subgraphs of density d>0 on linear subsets of vertices and being inseparable, in the sense that every cut has density at least mu>0, are sufficient assumptions for this problem. This generalises a recent result of Staden and Treglown.