Minimum degree conditions for powers of cycles and paths

Main Article Content

Eng Keat Hng


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.

Article Details

How to Cite
Hng, E. (2019). Minimum degree conditions for powers of cycles and paths. Acta Mathematica Universitatis Comenianae, 88(3), 795-800. Retrieved from