循環(huán)圖C（n;{1,k}）的交叉數(shù).pdf

1、圖的交叉數(shù)是衡量圖的非平面性的一個重要概念.Bhatt和Leighton指出一個網(wǎng)絡(luò)(圖)的交叉數(shù)是與這個圖VLSI電路設(shè)計需要的最小版圖面積是密切相關(guān)的.然而計算任意圖的交叉數(shù)是非常棘手的,Garey和Johnson證明了交叉數(shù)問題是NP完全的.迄今為止,只有很少圖族的交叉數(shù)是已知的.完全圖的交叉數(shù),完全二分圖的交叉數(shù)都是拓撲圖論中公開的難題.近年來,廣義Petersen圖,圈的交圖,循環(huán)圖等具有良好互連特性的圖族成為交叉數(shù)問題中活躍

2、的研究對象.Exoo等給出了P(n,2)的交叉數(shù),Fiorini給出了部分小階廣義Petersen圖的交叉數(shù).Sarazin證明了P(10,4)的交叉數(shù)是4.劉同印與劉彥佩給出了C(n;{1,2})的交叉數(shù).郝榮霞與劉彥佩給出了關(guān)于C(n;{1,k})交叉數(shù)的新上界.Richter和Salazar給出了P(n;3)的交叉數(shù).楊元生和趙承業(yè)給出了C(n;{1,n/2」})的交叉數(shù).Salazar給出了關(guān)于C(n;{1,k})和P(n,k)

3、通用的界.該文首先研究了循環(huán)圖C(n;(1,3))的交叉數(shù),證明了cr(C(n;{1,3}))= n/3」+nmod 3 for n≥8.這個結(jié)論證明了Richter,Salazar,郝榮霞,劉彥佩等關(guān)于循環(huán)圖C(n;(1,3))的交叉數(shù)的猜想是成立的.進一步,該文研究了循環(huán)圖C(n;{1, n/2」-1})的交叉數(shù),給出了n為偶數(shù)時交叉數(shù)的值和n為奇數(shù)時交叉數(shù)的上界.cr(C(n;{1,n/2-1})=n/2forevenn≥8.cr

4、(C(n;{1, n/2」-1})≤{4h+2, n=8h+1,h≥ 2;4h+2, n=8h+3, h≥2;4h+ 3, n=8h+ 5, h ≥ 1;4h+5, n=8h+7, h≥1.該文還研究了循環(huán)圖C(mk;{1,k})和廣義Petersen圖P(mk,k)的交叉數(shù).給出了C(mk;{1,k})交叉數(shù)的一個上界和C(3k;{1,k})交叉數(shù)的值,cr(C(3k;{1,k})=k for k≥3;cr(Cr(4k;{1,k})≤