|
系统科学与数学 2010
On the Crossing Number of K_{2,4}\times S_{n}
|
Abstract:
Garey and Johnson proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. In this paper, it is proved that the crossing number of the Cartesian product $K_{2,4}\times S_{n}$ is $Z(6,n)+4n.$ For $m\geq 5,$ we conjecture that ${\rm cr}(K_{2,m}\times S_{n})={\rm cr}(K_{2,m,n})+n\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor.$