The crossing number of Pn2□C3

AbstractThe exact crossing number is known only for a few specific families of graphs. Cartesian products of two graphs belong to the first families of graphs for which the crossing number has been studied. Let Pn be a path with n+1 vertices. Pnk, the k-power of the graph Pn, is a graph on the same vertex set as Pn and the edges that join two vertices of Pn if the distance between them is at most k. Very recently, some results concerning crossing numbers of Pnk were obtained. In this paper, the crossing numbers of the Cartesian product of Pn2 with the cycle Cm are studied. It is proved that the crossing number of the graph Pn2□C3 is 3n−3, and the upper bound for the crossing number of the graph Pn2□Cm is given