一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数  

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

作　　者：周志东[1] 李龙[1] 

机构地区：[1]衡阳师范学院数学与统计学院,湖南衡阳421002

出　　处：《运筹学学报》2016年第4期115-126,共12页Operations Research Transactions

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

摘　　要：图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3.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 specialgraph 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 Pn and with the cycle are cr（Q＋nK_1）=Z（6,n）＋2[n/2],cr（Q＋P_n）=Z（6,n）＋2[n/2]＋1 and cr（Q＋C_n）=Z（6,n）＋2[n/2]＋3

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

分 类 号：O157.5[理学—数学]