论文部分内容阅读
图的交叉数是衡量图的非平面性的一个重要概念.Bhatt和Leighton指出一个网络(图)的交叉数是与这个图VLSI电路设计需要的最小版图面积是密切相关的.然而计算任意图的交叉数是非常棘手的,Garey和Johnson证明了交叉数问题是NP完全的.迄今为止,只有很少图族的交叉数是已知的.完全图的交叉数,完全二分图的交叉数都是拓扑图论中公开的难题.近年来,广义Petersen图,圈的交图,循环图等具有良好互连特性的图族成为交叉数问题中活跃的研究对象.Exoo等给出了P(n,2)的交叉数,Fiorini给出了部分小阶广义Petersen图的交叉数.Sarazin证明了P(10,4)的交叉数是4.刘同印与刘彦佩给出了C(n;{1,2})的交叉数.郝荣霞与刘彦佩给出了关于C(n;{1,k})交叉数的新上界.Richter和Salazar给出了P(n;3)的交叉数.杨元生和赵承业给出了C(n;{1,n/2」})的交叉数.Salazar给出了关于C(n;{1,k})和P(n,k)通用的界.该文首先研究了循环图C(n;(1,3))的交叉数,证明了cr(C(n;{1,3}))= n/3」+nmod 3 for n≥8.这个结论证明了Richter,Salazar,郝荣霞,刘彦佩等关于循环图C(n;(1,3))的交叉数的猜想是成立的.进一步,该文研究了循环图C(n;{1, n/2」-1})的交叉数,给出了n为偶数时交叉数的值和n为奇数时交叉数的上界.cr(C(n;{1,n/2-1})=n/2forevenn≥8.cr(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.该文还研究了循环图C(mk;{1,k})和广义Petersen图P(mk,k)的交叉数.给出了C(mk;{1,k})交叉数的一个上界和C(3k;{1,k})交叉数的值,cr(C(3k;{1,k})=k for k≥3;cr(Cr(4k;{1,k})≤2k+1.for k≥3;cr(C(mk;{1,k}))≤min{(m-2)(k+1)-1,m(k-2)}for k≥3,m≥5.同时给出了P(mk,k)交叉数的一个上界和P(3k,k)的交叉数的值,cr(P(3k,k))=k for k≥4;cr(P(4k,k))≤2k+1 for k≥4;cr(P(mk,k))≤min{2mk+m-6k-5,m(2k-5)}for k≥4,m≥5.