P_(6)^(d=2)与特殊图联图的交叉数

The Crossing Number of Join Product of P^(d)_(6)=2 with Some Special Graphs

图的交叉数是图的一个重要参数,由于确定一般图类的交叉数已被证明是一个NP-完全问题,并且目前能够确定交叉数的图类甚少,因此关于图的交叉数问题仍值得研究。基于Kleitman关于完全二部图交叉数cr(K_(6, n))=Z(6,n)的基础上,文章运用数学归纳与反证的方法,研究并确定六阶图P_(6)^(d=2)与n个孤立点、路P_(n)和圈C_(n)联图的交叉数分别为cr(P_(6)^(d=2)+D_(n))=Z(6,n)+n,cr(P_(6)^(d=2)+P_(n))=Z(6,n)+n+1和cr(P_(6)^(d=2)+C_(n))=Z(6,n)+n+3。

The crossing number of a graph is an important parameter of the graph.Since determining the crossing number of a general graph class has been proved to be a NP-complete problem and there are few graph classes that can determine the crossing number,thus the issue of the crossing number of graphs is still worth studying.Based on the conclusion of Kleitman that the crossing number of the complete bipartite graph cr(K_(6,n))=Z(6,n),this article mostly uses mathematical induction and refutation to research and determine the crossing number of join product of the sixth-order graph P d=26 with n isolated vertices,the path P_(n) and the cycle C_(n) are cr(P^(d=2)_(6))+Dn=Z(6,n)+n,cr(P^(d=2)_(6)+P_(n))=Z(6,n)+n+1 and cr(P^(d=2)_(6))+C_(n)=Z(6,n)+n+3,respectively.