On the Crossing Numbers of the $k$-th Power of $P_n$

Abstract

Let $P_n$ be a path with $n$ vertices. $P_n^k$, the $k$-th power of the path $P_n$, is a graph on the same vertex set as $P_n$, and the edges that join all vertices $x$ and $y$ if and only if the distance between them is at most $k$. In this paper, the crossing numbers of $P_n^k$ are studied. Drawings of $P_n^k$ are presented and proved to be optimal for the case $n\le 8$ and for the case $k\le 4$.