【作者】 欧阳章东；

【导师】 黄元秋；

【作者基本信息】 湖南师范大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 自E．A．Norldaus，B．M．Stewart和A．T．White[1]等人于上世纪70年代初提出图的最大亏格概念以来，先后有许多图论学者都投身于这一拓扑参数的研究．由于N．H．Xuong[2],Y．P．Liu[3]等于上个世纪70年代末分别独立地给出了刻画图的最大亏格的表示定理和L．Nebesky[4]于上个世纪80年代初又给出了图的最大亏格的另一种对偶形式的刻画，因此关于图的最大亏格的研究取得了很重要的进步．上世纪90年代末，黄元秋的博士论文[5]对图的最大亏格进行了系统地研究及简化．目前，对于图的最大亏格研究主要集中在2个方面，一方面：希望能确定一些上可嵌入图类，即其最大亏格可取得最好的上界(?)；另一方面：希望得到一些非上可嵌入图类的由图的其它参数表示的最大亏格下界．本文主要从以上两方面进一步研究图的最大亏格，得到了一些新的上可嵌入图类，及一些图类的最大亏格较好的下界，推广了相关结果．本文的主要结果如下：(1)若G为2-边连通简单图，且满足以下条件之一：(a)α(G)≤2；(b)α(G)≥3，且对于任何彼此不相邻的三个顶点u_i(i=1，2，3)都有则G是上可嵌入的，其中下界“|V(G)|-3g(G)+7”是最好的．对于3-边连通图也有类似的结果．这推广了Y．C．Chen[6]的结果．(2)设G为k-边连通图，满足：其中k=1，2，3，则G是上可嵌入的．且不等式的上界是最好的．这推广了Y．C．Chen[7]的结果．(3)设G为k-边连通简单图，若对G中任意圈C，存在点x∈C满足：则G是上可嵌入的．且不等式的下界是最好的．关于这方面的结果，目前尚属首次．(4)设G是简单连通图，则ξ(G)≤α(G)／(?)，进而得到了最大亏格γM(G)的一个比较好的下界．改进了Y．Q．Huang[8]的结果．(5)首次研究边覆盖数与图的最大亏格下界的关系，得到：设G为k-边连通无环图，则进而得到了最大亏格γM(G)的一个比较好的下界．作为应用，改进了杨晓爱[9]的结果．更多还原

【Abstract】 Since the introductory investigation of maximum genus of graphs by E.A.Norldaus,B.M.Stewart,and A.T.White[1]in early 1970’s,many graph theoryscholars have studied the parameter of topology.On the maximum genus of graphs,some different necessary and sufficient conditions have been presented by N.H.Xuong[2]and Y.P.Liu[3]at the end of the 1970’s,respectively,and another form of dual characterization of maximum genus have been presented by L.Nebesky[4]inearly 1980’s.Thus,the reserch of maximum genus of graphs has been made veryimportant progress.At the end of the 199.0’s,the maximum genus of graphs hasbeen systematically studied and simplified in the Y.Q.Huang’s doctoral thesis[5].At present,the maximum genus of graphs mainly concentrated in the following twoareas:on the one hand,one wishes to find some classes of upper embeddable graphs,i.e.its maximum gennus reaches the best upper bound (?).On the other hand,one wishes to give the lower bound,which is expressed by the other parametersof graphs,on the maximum genus of non-upper embeddable graphs.This papermainly further studies the maximum genus of graphs from the above two areas,and provides some new classes of upper embeddable graphs,and gives some good lowerbounds of some classes of graphs.It has generalizes the relative results.The main results of the paper are as follows.(1)Let G be a 2-edge-connected simple graph,and if one of the followingconditions holds(a)α(G)≤2;(b)α(G)≥3,and for any three nonadjacent vertices v_i(i=1,2,3),it hasthen G is upper embeddable and the lower bound |V(G)|-3g(G)+7 is best possible. Similarly the result for 3-edge connected simple graph is also obtained.And itgeneralizes the results in Y.C.Chen[6].(2) Let G be a k-edge-connected graph.Ifwhere k=1,2,3,then G is upper embeddable and the upper bound is best possible.And it generalizes the results in Y.C.Chen[7].(3)Let G be a k-edge-connected simple graph,for any cycle C,there exist avetex x∈C,satisfies the following condition:then G is upper embeddable,and the lower bound is best possible.At present,thisresults in terms of the area is the first time.(4) Let G be a simple and connected graph,thenξ(G)≤α(G)/(?).And it obtains a better lower bound on the maximum genus of a graph.Meantime,itimproves the results in Y.Q.Huang[8].(5) The relationship of the edge covering number and the lower bound of themaximum genus is investigated firstly,and we obtain:Let G be k-edge connectedloopless graph,thenand thus give a good lower bound on the maximum genus.As an application,itimprove the results in X.A.Yang[9].更多还原