Minimum Degrees for Powers of Paths and Cycles

Abstrakt

We study minimum degree conditions under which a graph G contains kth 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 (2011), pp. 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.