论文部分内容阅读
1983年,Garey与Johnson证明:确定一个任意图的交叉数问题是Np-困难的(NP-complete).计算一个给定图的交叉数也是非常困难的,目前,只有很少图族的交叉数是已知的.完全图,完全二分图,广义Petersen图,交图,循环图等图族的交叉数等则是近年来交叉数领域研究的主要问题.
在交图的交叉数方向目前只给出了路径,圈以及星图与一些顶点数较少的图的交图的交叉数.
本文对路径与完全图的交图Km×Pn以及路径与完全二分图的交图Km,n×P1的交叉数进行研究.在这一研究方向,1994年Klesc给出cr(K4×Pn)=2n,2001年Klesc又给出了cr(K2,3×Pn)=2n,cr(K5×Pn)=6n.本文在此基础上,分别给出了路径与完全图的交图,路径与完全二分图的交图的交叉数上界:cr(Km×Pn)≤1/4[m+1/2][m-1/2][m-2/2](n[m+4/2]+[m-4/2]),m≥3,n≥1,cr(Km,n×P1)≤(l-1)([n+2/2][n+1/2][m/2][m-1/2]+m[n/2][n-1/2])+2([n+1/2][n/2][m/2][m-1/2]+[m/2][n/2][n-1/2],m≥2,n≥2,l≥1,及路径与完全图的交图的交叉数下界公式:cr(Km×Pn)≥(n-1)cr(Km+2-e)+2cr(Km+1),m≥3,n≥1,并且进一步确定了路径与完全图的交图,路径与完全二分图的交图中的一部分图,即当m=6时,K6×Pn以及m=2时,K2,n×P1的交叉数:cr(K6×Pn)=15n+3,n≥1,cr(K2,n×P1)=2l[n/2][n-1/2],n≥1,l≥1.
目前,已经确定了的交图的交叉数均为顶点数较少的图的交叉数,对于本文所研究的两类图,由于目前已知的顶点数较小时的交叉数均与本文所给的上界相符,本文猜想所给出的上界就是交叉数的值.