English

运筹学学报

• 运筹学 • 上一篇    

一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数

周志东1,*  李龙1   

  1. 1. 衡阳师范学院数学与统计学院, 湖南 衡阳  421002
  • 收稿日期:2016-02-29 出版日期:2016-12-15 发布日期:2016-12-15
  • 通讯作者: 周志东 zzdongwww@163.com
  • 基金资助:

    国家自然科学基金青年项目(No. 11401185), 湖南省重点建设学科项目, 湖南省重点实验室“智能信息处理与应用”, 湖南省自然科学基金青年人才联合培养基金(No. 14JJ6039), 衡阳师范学院科研启动基金(No. 13B39)

On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n

ZHOU Zhidong1,*   LI Long1   

  1. 2. College of Mathematics and Statistics, Hengyang Normal University, Hengyang 421002, Hunan, China
  • Received:2016-02-29 Online:2016-12-15 Published:2016-12-15

PDF

338

被引次数

2

摘要：

图的交叉数是图的一个重要参数，研究图的交叉数问题是拓扑图论中的前沿难题. 确定图的交叉数是~NP-难问题, 因为其难度, 能够确定交叉数的图类很少. 通过圆盘画法途径, 确定了一个特殊6点图与n个孤立点nK_{1}, 路P_{n}及圈C_{n}的联图的交叉数分别是cr(Q+nK_{1})=Z(6,n)+2\lfloor\frac{n}{2} \rfloor, cr(Q+P_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+1及cr(Q+C_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+3.

关键词: 画法, 交叉数, 圆盘画法, 联图, 路, 圈

Abstract:

The crossing numbers of a graph is a vital parameter and a hard problem in the forefront of topological graph theory.  Determining the crossing number of an arbitrary graphs is NP-complete problem. Because of its difficultly, the classes of graphs whose crossing number have been determined are very scarce. In this paper, for the special graph Q on six vertices, we through the disk drawing method to prove that the crossing numbers of its join with n isolated vertices as well as with the path P_{n} and with the cycle C_{n} are cr(Q+nK_{1})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor, cr(Q+P_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+1 and cr(Q+C_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+3, respectively.

Key words: drawing, crossing number, disk drawing, joint graph, path, cycle