The Crossing Numbers of Cartesian Product of Cone Graph \(C_{m} + \overline{K_{l}}\) with Path \(P_n\)

Abstract

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with small graphs. In this paper we study \(\text{cr}(W_{1,m} \Box P_{n})\), the crossing number of Cartesian product \(W_{l,m} \Box P_{n}\), where \(W_{l,m}\) is the cone graph \(C_{m} + \overline{K_{l}}\). Klešč showed that \(\text{cr}(W_{1,3} \Box P_{n}) = 2n\) (Journal of Graph Theory, \(6(1994), 605-614)\)), \(\text{cr}(W_{1,4} \Box P_{n}) = 3n – 1\) and \(\text{cr}(W_{2,3} \Box P_{n}) = 4n\) (Discrete Mathematics, \(233(2001),353-359\)). Huang \(et\) \(al\). showed that \(\text{cr}(W_{1,m} \Box P_{n}) = (n – 1)\lfloor\frac{m}{2}\rfloor \lfloor\frac{m-1}{2}\rfloor +n+1\). for \(n \leq 3\) (Journal of Natural Science of Hunan Normal University,\(28(2005), 14-16)\). We extend these results and prove \(\text{cr}(W_{1,m} \Box P_{n}) = (n – 1) \left\lfloor \frac{m}{2} \right\rfloor\lfloor \frac{m-1}{2}\rfloor + n+1\) and \(\text{cr}(W_{2,m} \Box P_{n}) = 2n \left\lfloor \frac{m}{2} \right\rfloor\lfloor\frac{m-1}{2} \rfloor + 2n\).