On the Crossing Number of K m □ P n

摘要

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(K m □ P n ), the crossing number of the Cartesian product K m □ P n . We prove that $cr(K_{m} square P_n)leq frac{1}{4}lfloorfrac{m+1}{2}rfloorlfloorfrac{m-1}{2} rfloorlfloorfrac{m-2}{2}rfloor(nlfloorfrac{m+4}{2} rfloor+ lfloorfrac{m-4}{2}rfloor)$ for m ≥ 3,n ≥ 1 and cr(K m □ P n )≥ (n ? 1)cr(K m+2 ? e) + 2cr(K m+1). For m≤ 5, according to Kle??, Jendrol and ??erbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr(K 6 □ P n ) = 15n + 3.