Some New Researches On The Maximum Genus Of Graphs

To study the drawing of a graph on a surface such that no two edges cross, which is an intuitive geometric problem, is the primitive objective of topological graph theory. Armed with other mathematical branches such as algebraic topology and group theory, and enumerative combinatorics, and the analysis of algorithms. topological graph theory has been becoming more and more meaningful.There are two fields in topological graph theory: one is the study of the properties of graph embedding. and the other is the enumerative theory of maps. This paper concerns the maximum genus of graphs which belongs to the first field.The embedding of a graph G on a surface S is such a homeomorphismΦ:G→S that each connected component of S-Φ(G) is homeomorphic to a open disk. According to S is orientable or nonoricntable surface, the embeddingΦof G on S is called orientable embedding or nonorientable embedding respectively. The maximum genusγ_M(G) of a connected graph G is the maximum integer k such that there exists an embedding of G into the orientable surface of genus k. Since any embedding must have at least one face, the Euler characteristic for one face leads to an upper bound on the maximum genuswhere the number |E(G)|- |V(G)|+1 is known as the Betti number (or cycle rank) of the connected graph G and is denoted byβ(G). A graph G is said to be up-embeddable ifγ_M(G)=(?).The idea of the maximum genusγ_M/(G) of a connected graph G was introduced by Nordhaus. Stewart and White [31] in 1971. In 1979, Liu[21] and Xuong|38] obtained the classical Theorem on the maximum genus independently. From then on. many researchers have studied the problem and obtained many interesting results. The research on maximum genus is mainly focused on two aspects: one is the study of the up-embeddability of graphs, and the other is the lower bound on the maximum genus of non-up-embeddable graphs. Because every graph is up-embeddable on non-orient able surfaces, the maximum genus problem only study orientable embeddings.This thesis consists of two parts: one is the deeper study of the maximum genus via the results obtained in the foretime: the other is an attempt on the studying of the maximum genus through joint tree, which is established by Liu Yanpei. The thesis are composed of the following six chapters:In chapter 1, the background of the maximum genus and some definitions and terminologies are provided.In chapter 2, the relation between the maximum genus and the edge-adding operation on graphs of diameter 3 are discussed.Chapter 3 is focused on the study of up-embeddability of graphs via girth and the degree-sum of adjacent vertices or nonadjacent vertices.In chapter 4 the lower bound of the maximum genus of graphs non-upembeddablc is discussed.Chapter 5 focuses on the study of the maximum genus of graphs via joint tree model.Chapter 6 consists of some problems worth studying further.