On the Crossing Numbers of the k-th Power of P n .
Wenping Zheng, Xiaohui S. Lin, Yuansheng Yang, GUI QIN YANG · Ars Combinatoria · 2009
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 <= 8 and for the case k <= 4.