The Upper Embeddablity Of Graphs

Maximum genus of graphs is a characteristic parameter, which determines a graph whether has a 2-cell embedding in a . certain orientable surface. The study of this parameter is one of the major problems of topological graph theory. While, the determination of a graph's upper embeddablity is to determine a graph's maximum genus. Combining one or more parameters of a graph, many papers either present some upper embeddable graphs^[7-14] that is to say, they present the graphs, whosemaximum genus reaches the best upper bound , or, theygive a better low bound on the maximum genus of some graphs^[15-31]The first major result of this paper is that: combining vertex partition and degree of vertices of graphs, to study the upper embeddablity of graphs. Let G be a graph, there exists a partition {v₁,V₂,.....V_k} of V(G] satisfying G[v₁] is a multiple complete graph for any i∈[l,k:],then G has a C- partition. This paper state such a result: Let G be a connected graph, and d_G(v)=1(mod4) for any V∈V(G), if the vertex-set of G has a C-partition satisfying and also o(mod4) for then G is upper-embeddable.The second major result of this paper is that: using the embedded character of a graph in a surface, especially the size of faces,to study the low bound on the maximum genus of a graph. In the paper [18],Professor Huang Yuanqiu and Liu Yanpei state a guess given by R.Nedeal and M.Skoviera in the paper[17].This guess is that: Let G be a simple graph, if there exists some surface- embedding making the size of every face of G no more than 7, then G is upper-embeddable, i.e.(G)≤l. At the same time,the paper [18] states that the condition of "the size of every face of G no more than 7"is necessary. Naturally, if there exists a face size more than 7 , then a worthy question arises' what about the upper bound of (G)?or to say, what about the low bound on the maximum genus of G ? The second major result of this paper will be answer this question.