Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (2): 10-18.

• Original Articles • Previous Articles     Next Articles

On the crossing numbers of W6*Sn

ZHOU Zhidong1,*,WANG Jing2   

  1. 1. Department of Mathematics and Computational Science, Hengyang Normal University, Hengyang 421002, Hunan, China 2. Department of Information and Computer Science, Changsha University, Changsha 410003, China
  • Received:2012-11-30 Online:2013-06-15 Published:2013-06-15

Abstract: In the early 1950s, Zarankiewicz conjectured that the crossing number of the complete partite graph K_{m,n}(m\leq n) is \lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor\lfloor\frac{n-1}{2}\rfloor (for any real number x, \lfloor x\rfloor denotes the maximum integer that is no more than x). At present, the truth of this conjecture has been proved for the case m\leq6. This paper determines the crossing number of the Cartesian product W_{6}  with S_{n} is cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor, provided that Zarankiewicz's conjecture holds for the case m=7.

Key words: crossing number, wheel, join product, star graph, Cartesian product

CLC Number: