English

运筹学学报 ›› 2013, Vol. 17 ›› Issue (2): 10-18.

• 运筹学 • 上一篇    下一篇

W6*Sn的交叉数

周志东1,*，王晶2   

  1. 1. 衡阳师范学院数学与计算科学系，湖南衡阳 421002 2. 长沙学院信息与计算科学系，长沙 410003
  • 收稿日期:2012-11-30 出版日期:2013-06-15 发布日期:2013-06-15
  • 通讯作者: 周志东 E-mail:zzdongwww@163.com
  • 基金资助:

    湖南省研究生科研创新基金 (No. CX2012B198), 湖南省“十二五”重点建设学科项目 (湘教发[2011]76 号)

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

PDF

818

摘要： 早在20世纪50年代，Zarankiewicz 猜想完全2-部图K_{m,n}(m\leq n)的交叉数为\lfloor\frac{m}{2}\rfloor\times \lfloor\frac{m-1}{2}\rfloor\times\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor (对任意实数x，\lfloor x\rfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当m\leq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立，确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor.

关键词: 交叉数, 轮, 联图, 星图, 笛卡尔积

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

中图分类号: