Extremal graphs of the $k$-th power of paths

Abstract

An extremal graph for a given graph $H$ is a graph with maximum number of edges on fixed number of vertices without containing a copy of $H$. The $k$-th power of a path is a graph obtained from a path and joining all pair of vertices of the path with distance less than $k$. Applying a deep theorem of Simonovits, we characterize the extremal graphs of the $k$-th power of paths. This settles a conjecture posed by Xiao, Katona, Xiao and Zamora in a stronger form.

9pages