On the crossing numbers of \(K_m\square C_n\) and \(K_{m,l}\square P_n\) (Q944744)

Let \(G_1\square G_2\) be the Cartesian product of two graphs \(G_1\) and \(G_2\). \textit{R. D. Ringeisen} and \textit{L. W. Beineke} [J. Comb. Theory, Ser. B 24, 134--136 (1978; Zbl 0383.05015)] have proved that \(cr(C_3\square C_n)=n\) and \(cr(K_4\square C_n)=3n\). \textit{D. Bokal} [J. Comb. Theory, Ser. B 97, 381--384 (2007; Zbl 1113.05027)] has proved that \(cr(K_{1,l}\square P_n)=(n-1)\lfloor \frac l2\rfloor\lfloor\frac{l-1}2\rfloor\). In this paper the authors study the crossing numbers of \(K_m\square C_n\) and \(K_{m,l}\square P_n\), and show that {\parindent=7mm \begin{itemize}\item[(i)]\(cr(K_m\square C_n)\geq n\cdot cr(K_{m+2})\) for \(n\geq3\) and \(m\geq5\); \item[(ii)]\(cr(K_m\square C_n)\leq\frac n4\lfloor\frac{m+2}2\rfloor\lfloor\frac {m+1}2\rfloor\lfloor\frac m2\rfloor\lfloor\frac{m-1}2\rfloor\) for \(m=5,6,7\) and for \(m\geq8\) with even \(n\geq4\), and equality holds for \(m=5,6,7\) and for \(m=8,9,10\) with even \(n\geq4\) and \item[(iii)]\(cr(K_{m,l}\square P_n)\leq(n-1)(\lfloor\frac{m+2}2\rfloor\lfloor\frac{m+1}2\rfloor\lfloor\frac{l+2}2\rfloor\lfloor\frac{l+1}2\rfloor-ml)+2(\lfloor\frac{m+1}2\rfloor\lfloor\frac m2\rfloor\lfloor\frac{l+1}2\rfloor\lfloor\frac l2\rfloor-\lfloor\frac m2\rfloor\lfloor\frac l2\rfloor)\) for \(\min(m,l)\geq2\), and equality holds for \(\min(m,l)=2\). \end{itemize}}