The Distribution Of Graph Embeddings And Relevant Properties

This thesis investigates the distribution of graph embeddings into topolog-ical surfaces and some relevant properties, by using graph embedding theory, Mohar’s overlap matrix theorem, Liu’s the joint tree model of graph embed-ding. Gross adding edges technique. and the White-Pisanaki theory etc. We concentrate on the total embedding distributions of graphs, genus distribu-tions of graphs, genus and crosscap number of cartesian products of graphs, genus and crosscap number of joins of graphs, the upper embeddability of graphs. They play important or key roles in the study of graph embedding in topological graph theory. Our main results can be stated as follows:1. In1989. Mohar showed a relationship between topological types of embedding surfaces and ranks of the corresponding overlap matrices. In1994, Chen, Gross and Rieper first used the overlap matrix for calculating the to-tal embedding distributions of necklaces, closed-end ladders and cobblestone paths. In Chapter2. also by using the overlap matrix, closed formulas of the total embedding distributions for two graph families obtained from the dipole D3are given.2. In1989. Furst. Gross and Statman first introduced the concept of closed-end ladder, and computed the genus distribution for it. In Chapter3, by using Liu’s the joint tree model of graph embedding, we obtain a recurrence relation about the genus distribution of closed-end double-ladders, and com-pute the number of embeddings of closed-end multi-ladders on the projective plane.3. Let (G, u,v) be a double-rooted connected graph with roots u and v, and G+e be the graph obtained by joining the roots u and v of (G, u, v) with an edge e. For the case that u and v are both2-valent, Gross showed a relationship between the genus distribution of G+e and the partitioned genus distribution of (G.u.v). In Chapter1. we generalize one of the two roots to arbitrarily high valence, and derive the genus distribution of G+e from the partitioned genus distributions of (G. u.v). 4. The maximum genus γ(G) of a graph G has the upper bound [3(G)/2], where B(G) denotes the Betti number. A graph G is said to be upper-embeddable if γM(G)=[β(G)/2].In [J. East China Normal University(Natural Science),5(2010),1-13], Han Ren et al. reviewed research developments on maximum genus of graphs in graph embedding theory since1971, and pre-sented the following two conjectures:(1) Let G be a simple connected graph such that each edge is contained in a triangle K3. Then G is upper-cmbeddable (2) Let c be an arbitrary positive number. Then, there exists a natural num-ber N(c) such that for every graph G of order n> N(c) and minimum degree5(G)≥cn, G is upper-embeddable. In Chapter5, we negate the above two conjectures, and discuss the condition for which the above conjectures is true.5. Let Km,m.m(m≥1) he a complete regular tripartite graph, and G be a bipartite graph with girth greater than1. In Chapter6, by using the White-Pisanski theory, the genus of cartesian product of Km,m,m with G is determined for A(G)<2m. Moreover, we obtain the crosscap number of cartesian product of Km,m,m with some nonbipartite graphs.(S. Let Gm and Cn be two disjoint cycles with m-vertex and n-vertex respectively. Gm+Gn denotes the join of Cm with Cn. When m>3and n>3or m=n=3. In Chapter7. we show that the genus of Gm+Cn is [(m-2)(n-2)/4] and the crosscap number of Cm+Cn is [(m-2)(n-2)/2].