Operations Research Transactions ›› 2014, Vol. 18 ›› Issue (2): 69-76.

• Original Articles • Previous Articles     Next Articles

On the crossing number of products of K_3,3 with S_n

OUYANG Zhangdong1,*, HUANG Yuanqiu2   

  1. 1. Department of Mathematics, Hunan First Normal University, Changsha 410205, China, 2. Department of Mathematics, Hunan Normal University, Changsha 410081, China
  • Online:2014-06-15 Published:2014-06-15

Abstract: Computing the crossing number of a graph is NP-complete. The results of crossing numbers of products of complete bipartite graph with stars are only very scarce up to date. In this paper, the relationship of crossing number for K_{3,3}\square S_n and K_{3,3,n} is established by some new contraction operations. Thus, a new approach to completely determine the crossing number of K_{3,3}\square S_n is provided.

Key words: complete bipartite, star, crossing number, contraction operation

CLC Number: