期刊论文

中文

运筹学学报

1007-6093

2013

17

2

10-18

10.15960/j.cnki.issn.1007-6093.2013.02.006

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

本校为第一机构

早在20世纪50年代,Zarankiewicz 猜想完全2-部图K_(m,n)(m≤ n)的交叉数为「m/2」×「m-1/2」×「n/2」×「n-1/2」 (对任意实数x,「x」表示不超过x的最大整数). 目前这一猜想的正确性只证明了当m≤6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立,确定了6-轮W_6与星S_n的笛卡尔积图的交叉是 cr(W_6× S_n)=9「n/2」×「n-1/2」+2n+5「n/2」.

In the early 1950s, Zarankiewicz conjectured that the crossing number ofthe complete partite graphKm,n（m≤n）is [m/2]×[m-1/2]×[n/2]×[n-1/2]（for any real numberχ,[χ]denotes the maximum integer that is no more than x）.At present, the truth of this conjecture has been proved for the case m ≤ 6. This paper determines the crossing number of the Cartesian product W6 with Sn is cr（W6×Sn）=9[n/2]×[n-1/2]＋2n＋5[n/2],provided that Zarankiewic...