On Genus Problems Of Some Kinds Of Graphs

In this paper, the lower bound problems of the maximum genus and the genus distributions of digraphs in orientable surfaces are studied. Intopological graph theory, the surface S is a compact 2-dimensional manifold without boundary. The orientable surface of genus i, denoted by Si, is the sphere with i handles added. A graph G is said to be embedded in a surface S if it is drawn in S so that edges intersect only at their common end vertices, and each region is homeomorphic to an open disk in the plane.The maximum genus of a connected graph G=(V,E), denoted by rM(G), is the maximum integer k with the property that there exists a 2-cellular embedding of G on the orientable surface with genus k. It can be seen that rM(G)≤|(β(G))/2| obviously.β(G)=|E(G)|-|V(G)|+1 is called the Betti number of the connected graph G, where|α| is said to be a biggest integer which is no more thanα. After the concept of the maximum genus of a connected graph rM(G) were given by E.Nordhaus,B.Stewart and A.T.White[1]. The problems of the maximal genus and upper embedding properties have received considerable attention. However, there are many kinds of graphs (for examples some 2-edge connected graphs and 3-edge connected graph) that are not upper-embeddable. Therefore, considerable attention is given to the lower bounds on the maximum genus of graphs.On the other side, two embeddings f:G→S and g:G→S of G into a surface S are said to be equivalent if there is a homeomorphism h:S→S, such that h0 f=g. Otherwise, they are said to be not equivalent. The genus distributions means the number of different embeddings (of equivalence classes) of graphs on surfaces. The genus problems were first introduced by Gross and Furst[2], then many people investigated these problems and obtained some results. But genus polynomials are unknown for most graphs, and most results about genus distributions graphs, little is known about genus distributions of digraphs.In this paper, we studied the lower bounds of maximum genus for 4-regular graphs and the genus distributions of two special graphs inorientable surfaces.In Chapter 1, we introduce the concepts and background of the maximum genus of graphs and graph embedding in orientable surface briefly.In Chapter 2, the structural characterization for a non-upper embeddable graph is used to split connected 4-regular graph, then the lower bounds of the maximum genus for connected 4-regular simple graphs and connected 4-regular graphs without loops are obtained by the proof of contradiction, the tightness of the lower bounds is proved.In Chapter 3, the joint tree method is generalized to digraph embeddings in orientable surfaces. The genus distributions on orientable surfaces of two types of digraphs:n times three-serial-digrphs and four-rings-digrphs are determined. Their maximum genus of directed embedding are obtained respectively. Then found that this two types of digraphs have same genus distributions inorientable surfaces.