On The Lower Bound Of Maximum Genus For Regular Graphs

ABSTRACT:In this paper, the lower bound of the maximum genus for regular graphs are studied.In topological graph theory, the surface S is a compact 2-dimensional manifold without boundary. The orientable surface of genus i, denoted by S., 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 such 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 yM (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.After the concept of the maximum genus of a connected graph yM(G) were given by E.Nordhaus^ B.Stewart and A.T.White[1]. The problems of the maximum 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.In this paper, we studied the lower bounds of maximum genus for regular graphs and prove that it is the best possible.Chapter 1, we introduce the concepts and background of the maximum genus of graphs and graph embedding in orientable surface briefly.Chapter 2, the structural characterization for a non-upper embeddable graph is used to split connected regular graph, then the lower bounds of the maximum genus for connected regular simple graphs are obtained by the proof with contradiction, the tightness of the lower bounds is proved.Chapter 3, the structural characterization for a non-upper embeddable graph is used to split connected regular graphs without loops, then the lower bounds of the maximum genus for some of connected regular graphs without loops are obtained by the proof with contradiction, the tightness of the lower bounds is proved.