【作者】 袁梓瀚；

【导师】 黄元秋；

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

【摘要】 图的交叉数是在近代图论中发展起来的一个重要概念,确定一般图的交叉数是一个NP-完全问题,因此到目前为止有关交叉数的结果很少,且仅限于一些特殊图类的交叉数.本文运用k-连通图限制画法下的求交叉数法、组合方法、归纳思想和反证法等,确定了一些特殊的图与路的笛卡尔积的交叉数,一类循环图的一点悬挂与两点悬挂的交叉数,这类循环图分别与路、星、树和圈的笛卡尔积的交叉数,及一类外平面图与圈的笛卡尔积的交叉数,并对Petersen图P（m,1）与路的笛卡尔积的交叉数进行了推广.全文由十个章节构成.第一章交代了交叉数的起源,交叉数研究在国内外发展的动态,以及这项研究工作的理论及实际意义.第二章对与交叉数有关的一些基本概念、定义和性质进行了解析或者说明,运用图的连通性得到了n—连通图和4—连通循环图C（l,2）的两个拷贝相交叉的一些性质等.第三章研究K_2,2,2和K_1,1,2,2的相关性质,并利用这些性质确定K_1,1,2,2与路P_n的交叉数.利用P（3,1）和K_2,4与路的交叉数的有关结果得到了三个特殊的六个顶点的图与路的交叉数.第四章在K_1,3,n和K_2,3,n交叉数的基础上,利用n-连通图相交叉的有关性质等,得到了七阶循环图C（7,2）与路P_n的笛卡尔积的交叉数和一个七阶3-连通图与路P_n的笛卡尔积的交叉数.第五章探索Petersen图P（4,1）与八阶循环图C（8,2）的相关性质,确定了C（8,2）和P（4,1）与路P_n的笛卡尔积的交叉数.第六章利用循环图C（l,2）的一点悬挂和两点悬挂的性质和画法等确定了C（l,2）的一点悬挂与两点悬挂的交叉数.第七章在C（7,2）和C（8,2）与路的笛卡尔积的交叉数的研究基础上,对原有的方法进行改进和推广,确定了循环图C（9,2）、C（10,2）和C（12,2）分别与路P_n的笛卡尔积的交叉数.第八章在假定Zarankiewicz猜想成立的基础上,由于循环图C（l,2）与路、星和树的笛卡尔积的交叉数研究的难度,我们采取限制C（l,2）的主圈上没有交叉点的措施,得出了循环图C（l,2）在限制条件下与路、星和树的笛卡尔积的交叉数.第九章限制C（l,2）的主圈上没有交叉点,得出了循环图C（l,2）在限制条件下与圈的笛卡尔积的交叉数的下界.同时还得到了一类外平面图与圈的笛卡尔积的交叉数.在最后一章中,简要地进行了总结,并介绍了作者今后研究的方向和重点及一些有待解决的问题.更多还原

【Abstract】 The crossing number of graphs is a vital concept in morden graph theory, we have already known that to determine the crossing numbers of graphs is NP-complete. At present the classes of graphs whose crossing numbers have been de-termined are very scarce,and there are only some special graphs whose crossing numbers are known.In this paper,we study the crossing numbers of the Cartesian products of paths,stars,cycles with circular graphs,a Petersen graph and some special graphs,and we discuss the crossing numbers of one suspension and a double suspension of circular graph C（l,2）,and explore the crossing numbers of the Cartesian products of outplanar graphs with cycles.At first,in Chapter one,we introduce the backgrouds and origins of the crossing number and its developments and recent situations around the world,and present the meanings of the research.In Chapter two,we give some conceptions and properties of the crossing number, and present the properties of n-connected graph and circular graphs and so on.In Chapter three,properties of K_2,2,2 and K_1,1,2,2 are investigated,and with the results of the crossing number of P（3,1） and K_2,4 with paths,the crossing numbers of Cartesian products of paths with K_1,1,2,2 and three speical 6-vertex graphs are determined.In Chapter four,applying the results of crossing numbers of K_1,3,n and K_2,3,n and the properties of n-connected graph,we obtain the crossing numbers of the Cartesian products of paths with circular graph C（7,2） and a 3-connected graph of seven vertices.In Chapter five,the properties of Petersen graph P（4,1） and the relations of P（4,1） and circlar graph C（8,2） being studied,the crossing number of Cartesian products of paths with C（8,2） and P（4,1） are determined.In Chapter six,by the properties and drawings of one suspension and a double suspension of circular graph C（l,2） which is 4-connected graph,we obtain the crossing numbers of one suspension and a double suspension of circular graph C（l,2）.In Chapter seven,we improve on the methods of chapter’s four and five,and determine the crossing numbers of Cartesian products of paths with circular graphs C（9,2）,C（10,2） and C（12,2）.In Chapter eight,supposing that the conjecture of Zarankiewicz is true,and letting there be no crossing points in the principle cyle of C（l,2）,we determine the crossing numbers of Cartesian product of paths,stars,trees with C（l,2）.In Chapter nine,letting there be no crossing points in the principle cyle of C（l,2）,we study the lower bound on the crossing numbers of Cartesian products of cycles with C（l,2）,and the crossing numbers of Cartesian products of cycles C_n with some outplanar graphs.In the last chapter,we make a summary of th paper and intruduce the directions of our research work and put forward some relative problems which we will go ahead.更多还原