运筹学学报 ›› 2014, Vol. 18 ›› Issue (2): 69-76.

• 运筹学 • 上一篇    下一篇

完全二部图K_{3,3}与星S_n的积图的交叉数

欧阳章东1,*, 黄元秋2   

  1. 1. 湖南第一师范学院数学系, 长沙 410205, 2. 湖南师范大学数学系, 长沙 410081
  • 出版日期:2014-06-15 发布日期:2014-06-15
  • 通讯作者: 欧阳章东 E-mail:oymath@163.com
  • 基金资助:

    国家自然科学基金 (Nos. 11301169, 11371133), 湖南省自然科学基金 (No. 13JJ4110), 湖南省教育厅资助科研项目 (No. 12B026),
    湖南省优秀博士学位论文获得者科研资助项目 (No. YB2013B040), 湖南第一师范学院科研项目 (No. XYS11N12)

On the crossing number of products of K_3,3 with S_n

OUYANG Zhangdong1,*, HUANG Yuanqiu2   

  1. 1. Department of Mathematics, Hunan First Normal University, Changsha 410205, China, 2. Department of Mathematics, Hunan Normal University, Changsha 410081, China
  • Online:2014-06-15 Published:2014-06-15

摘要: 确定图的交叉数是NP-完全问题. 目前有关完全二部图与星图的积图的交叉数结果并不多. 引入了一些新的收缩技巧, 建立了积图K_{3,3}\square S_n与完全三部图K_{3,3,n}之间的交叉数关系. 从而, 为进一步完全确定积图K_{3,3}\square S_n的交叉数提供了一条新途径.

关键词: 完全二部图, 星图, 交叉数, 收缩手术

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 contraction operations. Thus, a new approach to completely determine the crossing number of K_{3,3}\square S_n is provided.

Key words: complete bipartite, star, crossing number, contraction operation

中图分类号: