一个6点图与路的联图的交叉数

一个图G的交叉数cr(G)是把图G画在平面上,在所有画法中所产生的最少的交叉数.由于其结构的特殊性,能够确定两个图的联图交叉数的精确值的图类很少.本文通过圆盘画法这一途径,确定了一个特殊6点图与路P_n的联图的交叉数.

一类联图的交叉数

图的交叉数是表征一个图的非平面性的一个重要的参数。本文运用圆盘画法这一途径,确定了一个特殊6阶图与n个孤立点,n K_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+n K_1)=Z(6,n)+■2n/2」;cr(Q+P_n)=Z(6,n)+■2n/2」+1;cr(Q+Q_n)=Z(6,n)+■2n/2」+3。

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

图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是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.