Minimum Degree Conditions for Powers of Cycles and Paths

Eng Keat Hng, 22 Nov 2021

We study minimum degree conditions under which a graph \(G\) contains \(k\)-th powers of paths and cycles of arbitrary specified lengths. We determine precise thresholds, assuming that the order of \(G\) is large. This extends a result of Allen, Böttcher and Hladký [J. Lond. Math. Soc. (2) 84(2) (2011), 269–302] concerning the containment of squares of paths and squares of cycles of arbitrary specified lengths and settles a conjecture of theirs in the affirmative.