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 \leq 8\) and for the case \(k \leq 4\).