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}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)$, the crossing number of Cartesian product $W_{l,m}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n$, where $W_{l,m}$ is the cone graph $C_m+\overline{K_l}$. Klešč showed that $\text{cr}(W_{1,3}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)=2n$ (Journal of Graph Theory, $6(1994),605-614)$), $\text{cr}(W_{1,4}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)=3n–1$ and $\text{cr}(W_{2,3}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)=4n$ (Discrete Mathematics, $233(2001),353-359$). Huang $et$ $al$. showed that $\text{cr}(W_{1,m}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)=(n–1)\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor +n+1$. for $n\le 3$ (Journal of Natural Science of Hunan Normal University,$28(2005),14-16)$. We extend these results and prove $\text{cr}(W_{1,m}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)=(n–1)\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor +n+1$ and $\text{cr}(W_{2,m}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)=2n\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor +2n$.