Powers of Hamiltonian cycles in mu-inseparable graphs

Main Article Content

Oliver Ebsen Giulia Satiko Maesaka Christian Reiher Mathias Schacht Bjarne Schülke


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.

Article Details

How to Cite
Ebsen, O., Maesaka, G., Reiher, C., Schacht, M., & Schülke, B. (2019). Powers of Hamiltonian cycles in mu-inseparable graphs. Acta Mathematica Universitatis Comenianae, 88(3), 637-641. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1295/706