| 完全二部图K3,3与星Sn的积图的交叉数 |
| |
| 引用本文： | 欧阳章东,黄元秋.完全二部图K3,3与星Sn的积图的交叉数[J].运筹学杂志,2014(2):69-76. |
| |
| 作者姓名： | 欧阳章东 黄元秋 |
| |
| 作者单位： | [1]湖南第一师范学院数学系,长沙410205 [2]湖南师范大学数学系,长沙410081 |
| |
| 基金项目： | 国家自然科学基金（Nos.11301169,11371133）,湖南省自然科学基金（No.13JJ4i10）,湖南省教育厅资助科研项目（No.12B026）,湖南省优秀博士学位论文获得者科研资助项目（No.YB2013B040）,湖南第一师范学院科研项目（No.XYS11N12） |
| |
| 摘 要： | 确定图的交叉数是NP-完全问题．目前有关完全二部图与星图的积图的交叉数结果并不多．引入了一些新的收缩技巧，建立了积图K3,3□Sn与完全三部图K3,3□Sn之间的交叉数关系．从而，为进一步完全确定积图K3,3□Sn的交叉数提供了一条新途径．
|
| 关 键 词： | 完全二部图 星图 交叉数 收缩手术 |
On the crossing number of products of K3,3 with Sn |
| |
| 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 K3,3□Sn and K3,3,n is established by some new contraction operations. Thus, a new approach to completely determine the crossing number of K3,3□Sn is provided. |
| |
| Keywords: | complete bipartite star crossing number contraction operation |
| 本文献已被 维普 等数据库收录！ |
|
