摘要
Garey和Johnson证明了确定图的交叉数问题是一个NP-难问题.目前,已确定交叉数的图类并不多.本文证明了一个特殊6阶图与n个孤立点,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+n;cr(Q+P_n)=Z(6,n)+n+1及cr(Q+C_n)=Z(6,n)+n+3.
Garey and Johnson proved that the problem of determining the crossing numbet of an arbitrary graph is NP-complete. At present, there are few results concerning crossing numbers of some graphs. In the paper, for the special graph Q on six vertices, we prove that the crossing numbers of its join with n isolated vertices as well as with the path Pn and with the cycle Cr（Q＋nKl）=z（6,n）＋n;cr（Q＋R）=Z（6,n）＋n＋1 and cr（Q ＋ Cn） = Z（6, n） ＋ n ＋ 3.
出处
《数学进展》
CSCD
北大核心
2014年第1期69-80,共12页
Advances in Mathematics（China）
基金
国家自然科学基金数学天元基金项目(No.11226284)
湖南省教育厅资助项目(No.11C0541)
湖南省研究生科研创新基金资助项目(No.CX2012B198)
湖南省"十二五"重点建设学科资助项目(湘教发[2011]76号)
关键词
画法
交叉数
联图
路
圈
drawing
crossing number
joint graph
path
cycle
