| 一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数 |
| |
| 引用本文： | 周志东,李龙.一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数[J].运筹学学报,2016,20(4):115-126. |
| |
| 作者姓名： | 周志东 李龙 |
| |
| 作者单位： | 1. 衡阳师范学院数学与统计学院, 湖南 衡阳 421002 |
| |
| 基金项目： | 国家自然科学基金青年项目(No. 11401185), 湖南省重点建设学科项目, 湖南省重点实验室“智能信息处理与应用”, 湖南省自然科学基金青年人才联合培养基金(No. 14JJ6039), 衡阳师范学院科研启动基金(No. 13B39) |
| |
| 摘 要： | 图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2n/2],cr(Q+P_n)=Z(6,n)+2n/2]+1及cr(Q+C_n)=Z(6,n)+2n/2]+3.
|
| 关 键 词： | 画法 交叉数 圆盘画法 联图 路 圈 |
| 收稿时间： | 2016-02-29 |
On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n |
| |
| ZHOU Zhidong,LI Long.On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n[J].OR Transactions,2016,20(4):115-126. |
| |
| Authors: | ZHOU Zhidong LI Long |
| |
| Institution: | 2. College of Mathematics and Statistics, Hengyang Normal University, Hengyang 421002, Hunan, China |
| |
| 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. |
| |
| Keywords: | drawing crossing number disk drawing joint graph path cycle |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
