On Maximum Genus And Other Invariants Of Graphs

Embedding of a graph on surface originated from the proof of Map Color Theorem. Here, surface S is a compact 2-dimensional manifold without boundary, which includes orientable or nonorientable surface [6]. The embedding of a connected graph G on surface S is a homeomorphismφ:G→S such that each connected component of S-φ(G) is homeomorphic to an open disk. The genus,γ(G), of a connected graph G is the minimum integer n such that there exists an embedding of G on the orientable surface Sn with genus n. The maximum genus,γM(G), of a connected graph G is the maximum integer n such that there exists an embedding of G on the orientable surface Sn with genus n. In 1966, Duke[12] obtained that if a connected graph G can be embedded on the orientable surface Sn and Sm(n≤m), then G can be embedded on the orientable surface Sg, n≤g≤m. Hence, the genus and the maximum genus of G determine all the orientable surfaces on which G can be embedded. Similarly, we can define the maximum nonorientable genus of a connected graph G, denoted byγm(G). On the maximum nonorientable genus of a connected graph G, Liu [36], Ringel[50] and Stahl[59] proved independently that So, we only need to study the maximum genus of a connected graph.Any embedding on the orientable surface has at least one face. By Euler Formula, it is easy to obtain that Where,β(G)=ε(G)-ν(G)+1 is the Betti number of G. IfγM(G)=「β(G)/2」, then G is called up-embeddable.In this thesis, by combining some invariants such as the minimum degree, girth, the number of vertices, independent number and the degree sum of vertices etc, we obtain some new results on up-embeddability and a new lower bound on maximum genus. In the following, we will introduce the content of each chapter briefly. In Chapter 1, firstly, we give a brief introduction on some concepts and the background of graph embedding. Secondly, we introduce some terminologies on graph theory and some basic properties on maximum genus.In Chapter 2, combining minimum degree and girth of a graph, by studying the number of vertices of the given subgraphs, we obtain the relation between the up-embeddability and the number of vertices of a graph.In Chapter 3, by combining minimum degree and girth of a graph, we obtain a new lower bound on maximum genus of a graph.In Chapter 4, combining the girth of a graph, by studying the degree sum of adjacent vertices of the given subgraphs, we obtain the relation between the up-embeddability and the degree sum of adjacent vertices of a graph.In Chapter 5, combining minimum degree and girth of a graph, by study-ing the independent number, the degree sum of nonadjacent vertices of the given subgraphs, we obtain the relation between the up-embeddability and independent number, the degree sum of nonadjacent vertices of a graph.In Chapter 6, we study the structure of the 2-edge connected 3-regular nonup-embeddable graphs, and complement the result on 2-edge connected 3-regular up-embeddable graphs [28].In Chapter 7, we pose some questions for further study, such as the enumer-ation of the maximum genus embedding, the study of relative maximum genus, using joint tree model to study maximum genus etc.