On Minimum Genera Of Given Graphs

The embeddability of a graph on a surface is a major theme of topological graph theory.Since the minimum genus problem is NP-complete,one does not hope to find a minimum genus formula for an arbitrary graph.Considering the hardness in computational complexity,in this paper,by applying the joint tree model introduced by Yanpci Liu,we seek to isolate interesting and signifieative families of graphs for which the formulae of minimum genera can be derived. In addition,genus distributions of orientable embeddings for given graphs arc provided. This paper much advances the art of calculating genus problems.The method used here offers considerable promise of application to additional families of graphs beyond the ones for which it yields formulae here.For studying the minimum genus of a graph,based on the joint trees,an embedding of a graph on a surfacc can be represented by a joint tree,further by an associated surface of it.Divide the associated surface into segments layer by layer and define an operation called an exchanger in the layer division.Hence the associated surface of minimum genus can be got by doing a sequence of exchangers on some associated surface.Further,according to the properties of given graphs, the expressions of minimum genera of these graphs are obtained.These are apparently not easily obtained using quotient embcddings.The content of this part is concentrated on the first five chapters.In chapter 1,firstly,we give a brief introduction about the background of two parts.Then some definitions and properties,related to them,are provided.Chapter 2,obtains the minimum genus of complete bipartite graphs with a different method as before.Based on the properties of associated surfaces for complete bipartite graphs,a new type of graph J(m,n) with weak symmetry is constructed.At the same time,the minimum genus of it is derived.Finally,the number of genus embeddings of complete bipartite graphs is easily estimated.In chapter 3,we construct a new type of graph T(n,l,m) with weak symmetry and compute the minimum genus of it.As a corollary,the minimum genus of complete tripartite graph K_n,n,l(l≥n≥2) is also derived.Finally,the number of genus embeddings of complete tripartite graph K_n,n,l is easily estimated. Chapter 4,discusses the minimum genera of edge amalgamations of given graphs.Lit.[1,2]study the minimum genera of edge amalgamations for complete graphs and complete bipartite graphs,respcctivly.Here,the minimum genera of edge amalgamations for n given graphs are obtained.In chapter 5,we study the minimum genus of joins of several types of graphs with a vertex.And the joins of planar graphs with a vertex are apex graphs.It is well known that apex graphs are far more important graphs of topological graph theory and play an important role in research of minimum genus of a graph.Mohar proved that minimum genus problem is NP-hard.Here,the minimum genera of joins of several types of planar graphs with a vertex,namely apex graphs,and two types of graphs with a vertex,are provided,where the two types of graphs may not be planar.The second part which includes chapter 6,mainly generalizes the class of " beads ",beyond those appearing in[21],for which genus distribution calculations are tractable.By basing the calculation on the explicit choice of a spanning tree and classifying the associated surfaces according to the properties of given graphs,some equations are obtained to compute the explicit expressions of genus distributions for the given graphs.Further,this permits one to obtain formulae for infinite families of regular graphs with degree greater than 3 and 4 and with arbitrary many vertices.Chapter 6,firstly,constructs generalized necklaces,circulant necklaces and another three types of graphs by generalizing necklaces,then obtains the explicit expressions of orientable embedding distributions by genus for them.Finally,further generalizes the given graphs to obtain a new type of graph and gives a description about genus distribution of orientable embeddings for this type of graph.Chapter 7,discusses some unresolved problems about minimum genus and genus distribution of orientable embeddings for a graph,such as based on the joint tree model,calculation of minimum genus of complete graphs,determination of minimum genera for further types of graphs or even arbitrary graphs,etc.