运筹学学报 >
2016 , Vol. 20 >Issue 4: 115 - 126
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.04.014
一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数
收稿日期: 2016-02-29
网络出版日期: 2016-12-15
基金资助
国家自然科学基金青年项目(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
Received date: 2016-02-29
Online published: 2016-12-15
图的交叉数是图的一个重要参数，研究图的交叉数问题是拓扑图论中的前沿难题. 确定图的交叉数是~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.
周志东, 李龙 . 一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数[J]. 运筹学学报, 2016 , 20(4) : 115 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.014
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
/
| 〈 |
|
〉 |
