【作者】 王晶；

【导师】 黄元秋；

【作者基本信息】 湖南师范大学 ， 基础数学， 2009， 博士

【摘要】 图的交叉数问题,起源于二战期间Pual Tur(?)n在砖厂碰到的一个实际难题,逐渐发展成为图论学科中非常活跃的一个分支,吸引着国内外许多学者的关注.然而,确定一般图的交叉数是一个NP-完全问题,因此,到目前为止有关交叉数的结果比较少,仅限于一些特殊简单图的交叉数.甚至在许多情况下,试图找出图的交叉数的一个好的上界或下界也很困难.本文运用组合方法和归纳思想以及反证法,确定了一些特殊图类,如广义Petersen图P(3k,k),循环图C(3k-1;{1,k}),W_m×P_n,两个特殊的六阶图与星S_n的笛卡尔积图,星图S_m与路P_n、星图S_m与圈C_n的联图的交叉数的精确值或者其上、下界,并试图研究交叉数的一般性质,从画法上着手得到了一个好画法为最优画法的充分条件.全文由9个章节组成.第一章较为详细地交代了交叉数的起源,研究工作的理论与实际意义,以及目前交叉数研究在国内外的发展动态.同时还简要介绍了本文的主要结构.第二章介绍了阅读本文所要用到的图的交叉数方面的基本概念和预备知识.第三章得到了当k≥4时,广义Petersen图P(3k,k)的交叉数为k.第四章讨论了当k≥3时,循环图C(3k-1;{1,k})交叉数的上界和下界.第五章确定了对任意的m≥3和n≥1,轮W_m与路P_n的笛卡尔积图的交叉数.第六章对两个特殊的六阶图与星S_n的笛卡尔积图的交叉数进行了研究.第七章讨论了当m=3,4,5时,星S_m与路P_n的联图的交叉数,和当m=3,4时,星S_m与圈C_n的联图的交叉数.第八章研究图的交叉数的一般性质,并从画法上着手得到了一个好画法为最优画法的充分条件.第九章给出了本文的总结和对未来工作的展望.更多还原

【Abstract】 The crossing number of graphs comes from the Pual Tur(?)n’s brick factory problem during the World WarⅡ, and it becomes a very active branch in Graph Theory, many authors have studied this area. However, determining the crossing number of graphs is NP-complete. Because of its difficulty, there are only very scarce special classes of graphs whose crossing numbers are determined. Even in some cases, it is very difficult to find the upper or lower bounds of the crossing number of graphs. In this paper, we study the crossing number of some special graphs, such as the generalized Petersen graph P(3k,k), the circulant graph C(3k-1;{1,k}), the Cartesian product of S_n with two special 6-vertex graphs, W_m×P_n,S_m∨P_n,S_m∨C_n,etc. The paper is consist of 9 chapters:In chapter one, we introduce the origins and backgrounds of the crossing number, its theorical and practical meanings, and its development around the world.Chapter two gives some conceptions and properties of the crossing number, and introduces the required knowledge for reading this paper.Chapter three determines that the crossing number of the generalized Petersen graph P(3k,k) is k for arbitrary k≥4.Chapter four studies the upper and lower bounds of the crossing number of the circulant graph C(3k-1;{1, fe}) for k≥3.Chapter five investigates the crossing number of Cartesian product of the wheel W_m with path P_n for m≥3 and n≥1.In chapter six, the crossing numbers of the Cartesian product of S_n with two special 6-vertex graphs are determined.Chapter seven studies the crossing numbers of S_m∨P_n for m= 3,4,5 and for all n, and the crossing numbers of S_m∨C_n for m = 3,4 and for all n.Chapter eight investigates the general property of the crossing number of graphs, and presents a sufficient condition to enforce a good drawing to be optimal. In the last chapter, we make some conclusions of our research work and put forward some relative problems which we will go ahead.更多还原