| 完全二部图K_{3,3}与星S_n的积图的交叉数 |
| |
| 引用本文： | 欧阳章东,黄元秋.完全二部图K_{3,3}与星S_n的积图的交叉数[J].运筹学学报,2014,18(2):69-76. |
| |
| 作者姓名： | 欧阳章东 黄元秋 |
| |
| 作者单位： | 1. 湖南第一师范学院数学系, 长沙 410205,
2. 湖南师范大学数学系, 长沙 410081 |
| |
| 基金项目： | 国家自然科学基金(Nos.11301169,11371133);湖南省自然科学基金(No.13JJ4110);湖南省教育厅资助科研项目(No.12B026);湖南省优秀博士学位论文获得者科研资助项目(No.YB2013B040);湖南第一师范学院科研项目(No.XYS11N12) |
| |
| 摘 要： | 确定图的交叉数是NP-完全问题. 目前有关完全二部图与星图的积图的交叉数结果并不多. 引入了一些新的收缩技巧, 建立了积图K_{3,3}\square S_n与完全三部图K_{3,3,n}之间的交叉数关系. 从而, 为进一步完全确定积图K_{3,3}\square S_n的交叉数提供了一条新途径.
|
| 关 键 词： | 完全二部图 星图 交叉数 收缩手术 |
On the crossing number of products of K_3,3 with S_n |
| |
| OUYANG Zhangdong,HUANG Yuanqiu.On the crossing number of products of K_3,3 with S_n[J].OR Transactions,2014,18(2):69-76. |
| |
| Authors: | OUYANG Zhangdong HUANG Yuanqiu |
| |
| Institution: | 1. Department of Mathematics, Hunan First Normal University, Changsha 410205, China,
2. Department of Mathematics, Hunan Normal University, Changsha 410081, China |
| |
| 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 contractionoperations. Thus, a new approach to completely determine the crossing number of K_{3,3}\square S_n is provided. |
| |
| Keywords: | complete bipartite star crossing number contraction operation |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
