| W6*Sn的交叉数 |
| |
| 引用本文： | 周志东,王晶. W6*Sn的交叉数[J]. 运筹学学报, 2013, 17(2): 10-18 |
| |
| 作者姓名： | 周志东 王晶 |
| |
| 作者单位： | 1. 衡阳师范学院数学与计算科学系，湖南衡阳 421002 2. 长沙学院信息与计算科学系，长沙 410003 |
| |
| 基金项目： | 湖南省研究生科研创新基金，湖南省"十二五"重点建设学科项目 |
| |
| 摘 要： | 早在20世纪50年代，Zarankiewicz 猜想完全2-部图K_{m,n}(mleq n)的交叉数为lfloorfrac{m}{2}rfloortimes lfloorfrac{m-1}{2}rfloortimeslfloorfrac{n}{2}rfloortimeslfloorfrac{n-1}{2}rfloor (对任意实数x，lfloor xrfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当mleq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立，确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}times S_{n})=9lfloorfrac{n}{2}rfloortimeslfloorfrac{n-1}{2}rfloor+2n+5lfloorfrac{n}{2}rfloor.
|
| 关 键 词： | 交叉数 轮 联图 星图 笛卡尔积 |
| 收稿时间： | 2012-11-30 |
On the crossing numbers of W6*Sn |
| |
| ZHOU Zhidong , WANG Jing. On the crossing numbers of W6*Sn[J]. OR Transactions, 2013, 17(2): 10-18 |
| |
| Authors: | ZHOU Zhidong WANG Jing |
| |
| Affiliation: | 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 |
| |
| Abstract: | In the early 1950s, Zarankiewicz conjectured that the crossing number of the complete partite graph K_{m,n}(mleq n) is lfloorfrac{m}{2}rfloorlfloorfrac{m-1}{2}rfloorlfloorfrac{n}{2}rfloorlfloorfrac{n-1}{2}rfloor (for any real number x, lfloor xrfloor denotes the maximum integer that is no more than x). At present, the truth of this conjecture has been proved for the case mleq6. This paper determines the crossing number of the Cartesian product W_{6} with S_{n} is cr(W_{6}times S_{n})=9lfloorfrac{n}{2}rfloorlfloorfrac{n-1}{2}rfloor+2n+5lfloorfrac{n}{2}rfloor, provided that Zarankiewicz's conjecture holds for the case m=7. |
| |
| Keywords: | crossing number wheel join product star graph Cartesian product |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
