On the nonplanarity of powers of paths

Abstract

For a positive integer k, the kth. power P^k_n of a path P_n of order n consists of the vertices of P_n where two vertices x and y of P_nare adjacent in P^k_n if and only if 1 < d(x, y) ≤ k. For k ≥ 4 and n ≥ 5, the graph P^k_n. It is nonplanar. It is shown that the crossing number of P⁴_n is n - 4 for each n ≥ 4 and the crossing number of P⁵₇ is 6. A necessary and sufficient condition is presented for PP⁵₇ to contain topological complete multipartite graphs.