路徑與完全圖，完全二分圖的交圖的交叉數(shù).pdf

1、1983年，Garey與Johnson證明：確定一個任意圖的交叉數(shù)問題是Np-困難的(NP-complete).計算一個給定圖的交叉數(shù)也是非常困難的，目前，只有很少圖族的交叉數(shù)是已知的.完全圖，完全二分圖，廣義Petersen圖，交圖，循環(huán)圖等圖族的交叉數(shù)等則是近年來交叉數(shù)領域研究的主要問題. 在交圖的交叉數(shù)方向目前只給出了路徑，圈以及星圖與一些頂點數(shù)較少的圖的交圖的交叉數(shù). 本文對路徑與完全圖的交圖Km×Pn以及路徑與

2、完全二分圖的交圖Km,n×P1的交叉數(shù)進行研究.在這一研究方向，1994年Klesc給出cr(K4×Pn)=2n，2001年Klesc又給出了cr(K2,3×Pn)=2n，cr(K5×Pn)=6n.本文在此基礎上，分別給出了路徑與完全圖的交圖，路徑與完全二分圖的交圖的交叉數(shù)上界：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)([

3、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，及路徑與完全圖的交圖的交叉數(shù)下界公式：cr(Km×Pn)≥(n-1)cr(Km+2-e)+2cr(Km+1)，m≥3，n≥1，并且進一步確定了路徑與完全圖的交圖，路徑與完全二分圖的交圖中的一部分圖，即當m=6時，K6×Pn以及m=2時，K2,n