Research On The Maximum Genus Of Graph

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].