| ABSTRACT:In this thesis, we study the embeddings of graphs on surfaces. It contains two parts. Firstly (includes Chapter 2, Chapter 3 and Chapter 4), based on the conclusions of Chapter 2, the analysing of the conjecture proposed by Stiebitz et. al. in [Journal of Combinatorial Theory, Series B 96 (2006) 20-37] are given in Chapter 3 are Chapter 4 and:Conjecture Let G be the edge disjoint union of a complete graph K and an arbitrary graph H. Let H' be the graph obtained from G by contracting the set V(K) to a single vertex. Thenγ(K)+γ(H')<γ(G).Embedding a graph on surfaces, by getting a surface of the graph with the minimum genus embedding, then using the properties of polygon representation of a surface, we obtains genus equalities and genus inequalities for certain graphs with specific properties.Secondly (includes Chapter 5, Chapter 6 and Chapter 7), the classification of graph embeddings on surfaces are discussed, that is to determine the number of (nonequivalent) embeddings of graph on surfaces. It is an important problem in the study of a graph embedding in topological graph theory. The graphs considered in this thesis are all connected graphs and the surface is a compact 2-dimensional manifold without boundary.An embedding of a graph G into a surface S is a homeomorphism h:G→S of G into S such that every component of S-h(G) is a 2-cell. This type of embedding is also called cellular embedding. Every minimum genus embedding of a connected graph is cellular.Two embeddings h:G→S and g:G→S of G into an orientable surface S are said to be equivalent if there is an orientation preserving homeomorphism f:S→S such that f oh=g. Researching on this problem can be tracked back to 1980s when Gross and Furst were studying the hierarchy for embedding invariants of a graph, then it has been developed and deepened by many researchers. In the following, we will introduce the content of each chapter of this thesis briefly.In Chapter 1, firstly, we look back the development of the graph theory and introduce briefly the Heawood problem whose solution gave topological graph the- ory the critical momentum to develop into an independent research area. Then we give a brief introduction on concepts and background of graph embedding, intro-duce the concepts of the polygonal representations of surfaces and the joint tree model of graph embedding etc. Finally, we introduce the structure and the content of each chapter of this thesis briefly.In Chapter 2, based on the joint tree model and the polygonal representations of surfaces, we study mainly that the minimum genus embeddings of a graph, the polygonal representations of the embedding surfaces and their mutual relations. We get two well-known genus equalities theorems.In Chapter 3, we analyse the conjecture, by using a combinatorial way, and show that theorem 3.1 constructively, then by using the relation between a graph who is edge disjoint union of two graphs and other graph who is vertex disjoint union of two graphs, we obtain theorem 3.2. A complete graph is a hamiltonian graph, therefore the conjecture is true.In Chapter 4, we continuously study the conjecture based on the algebraic way, we show that theorem 4.1, then we obtain theorem 4.2. A complete graph is a connected graph, therefore the conjecture is a corollary of theorem 4.2.In Chapter 5, based on the conclusions of the ladder graphs, we study the genus distribution of the pearl-ladder by dividing the associate surfaces into 11 types.In Chapter 6, we obtain the genus polynomials of a ladder-ladder graphs by using the two ways, one is a surface generating method, the other is a surface sorting method.In Chapter 7, we study the distribution for similar benzene structure graphs. By joint trees of the graph and using two transforms that satisfying the associate surfaces of the joint trees, we divide the sets of the associate surfaces into 10 types. Based on these, we get the distribution for similar benzene structure graphs.In Chapter 8, we posed some questions for further study.
|
PDF Full Text Request