循环图C（n；{1，k}）的交叉数

【作者】 吕建国；

【导师】 杨元生；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2004， 硕士

【摘要】 图的交叉数是衡量图的非平面性的一个重要概念。Bhatt和Leighton指出一个网络(图)的交叉数是与这个图VLSI电路设计需要的最小版图面积是密切相关的。然而计算任意图的交叉数是非常棘手的，Garey和Johnson证明了交叉数问题是NP完全的。迄今为止，只有很少图族的交叉数是已知的。完全图的交叉数，完全二分图的交叉数都是拓扑图论中公开的难题。 近年来，广义Petersen图，圈的交图，循环图等具有良好互连特性的图族成为交叉数问题中活跃的研究对象。Exoo等给出了P(n，2)的交叉数，Fiorini给出了部分小阶广义Petersen图的交叉数。Sarain证明了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))的交叉数，证明了这个结论证明了Richter，Salazar，郝荣霞，刘彦佩等关于循环图C(n；(1，3))的交叉数的猜想是成立的。 进一步，本文研究了循环图的交叉数，给出了n为偶数时交叉数的值和n为奇数时交叉数的上界。 本文还研究了循环图C(mk；{1，k})和广义Petersen图P(mk，k)的交叉数。给出了C(mk；{1，k})交叉数的一个上界和C(3k；{1，k})交叉数的值，同时给出了P(mk，k)交叉数的一个上界和P(3k，k)的交叉数的值，更多还原

【Abstract】 Crosssing number is an important concept measuring the non-planarity of graphs. Bhatt and Leighton showed the corssing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. However, it is intractable to calculate the crossing number of an arbitrary graph. Garey and Johnson have showed crossing number is NP-Complete. There are only a few infinite families of graphs whose crossing numbers are known. The crossing numbers of the complete bipartite graph and the complete graph are open problems in topological graph theory.Recently, many mathematicians focus on some graphs with good properities, such as the generalized Petersen graph, CmxCn and the circulant graph. Exoo et al. showed the crossing number of P(n,2). Fiorini showed crossing numbers of some generalized Petersen graphs with small order. Sarazin proved that the crossing number of P(10,4) is four. Liu Tongyin and Liu Yanpei showed the crossing number of C(n;{l,2}). Hao Rongxia and Liu Yanpei showed a new bound for crossing numbers of C(n;{1,k}). Richter and Salazar showed the crossing number of P(n;3). Yang Yuansheng and Zhao Chengye showed crossing numbers of C(n;{1l,n/2}). Salazar showed tight bounds for crossing numbers of C(n;{1,k}) and P(n,k).Firstly, it is proved that the crossing number of C(n; {1,3}) isIt verifies the conjecture proposed by Richter, Salazar, Hao Rongxia and Liu Yanpei.Secondly, this paper focuses on the crossing number of C(n;(1,n/2-1)). The value of crossing numbers for even n and the upper bound for crossing numbers for odd n are showed. for even n>8.Finally, crossing numbers of C(mk;{1,k}) and P(mk,k) are studied in this paper. Some close upper bounds and some exact values are showed.cr(C(3k;{1,k}) = k for k>3;cr(C{4k;{1,k})<2k + 1 for k>;cr(C(mk;{1,k})) <min{(m-2)(k +1)-1,m(k-2)} for k>,m>5.cr(P(3k,k)) = k for k>; cr(P(4k,k))<2k +1 for k>;cr(P(mk,k))<min{2mk + m-6k-5,m(2k-5)} for k>,m>.更多还原