Minimum degree conditions for powers of cycles and paths

Abstract

The study of conditions on vertex degrees in a host graph G for the appearance of a target graph H is a major theme in extremal graph theory. The kth power of a graph F is obtained from F by joining any two vertices at distance at most k. We study minimum degree conditions under which a graph G contains the kth power of cycles and paths 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ý concerning the containment of squared paths and squared cycles of arbitrary specified lengths and settles a conjecture of theirs in the affirmative.