W6×Sn的交叉数

• 作 者: 周志东 王晶
• 机 构: 衡阳师范学院数学与计算科学系,长沙学院信息与计算科学系
• 出 处: 运筹学学报
• 发表日期: 2013年2期
• 关键词: 交叉数 轮 联图 星图 笛卡尔积 crossing number wheel join product star graph Cartesian product
• 基金项目: 湖南省研究生科研创新基金（No.CX20128198）,湖南省“十二五”重点建设学科项目（湘教发[2011]76号）

早在20世纪50年代，Zarankiewicz猜想完全2-部图Km,n（m≤n）的交叉数为[m/2]×[m-1/2]×[n/2]×[n-1/2]（对任意实数χ,[χ]表示不超过χ的最大整数）．目前这一猜想的正确性只证明了当m≤6时成立．假定著名的Zarankiewicz的猜想对m=7的情形成立，确定了6-轮W6眠与星Sn的笛卡尔积图的交叉是cr（W6×Sn）=9[n/2]×[n-1/2]＋2n＋5[n/2].