【作者】 郭婷；

【导师】 黄元秋；

【作者基本信息】 湖南师范大学 ， 基础数学， 2013， 博士

【摘要】 本文利用拓扑图论中图的可嵌入性理论,Mohar勺覆盖矩阵法,刘彦佩的图嵌入的联树模型,Gross的加边技巧,以及White-Pisanski理论等,研究图在曲面上的嵌入分布和一些相关的性质.其主要研究内容包括图的完全嵌入分布、图的亏格分布、笛卡尔积图的亏格和交叉帽数、联图的亏格和交叉帽数、图的上可嵌入性等.它们是拓扑图论中关于图的嵌入研究的一些重要或关键问题.本文取得的结果主要在以下几个方面：1.1989年,Mohar给出了嵌入曲面的拓扑类型与对应的覆盖矩阵的秩之间的关系.1994年,Chen, Gross和Rieper首次利用覆盖矩阵方法,计算了necklaces, closed-end ladders和cobblestone paths的完全嵌入分布.本文第二章,我们进一步应用Moliar的覆盖矩阵,得到了由双极图D3所构成的两类图的完全嵌入分布.2.1989年,Furst, Gross和Statman首次引进闭梯图(closed-end ladders)并得到其亏格分布.本文第三章,利用刘彦佩创建的嵌入的联树模型,得到了二重闭梯图(closed-end donble-laddcrs)的亏格分布的一个递推关系,并进一步给出了多重闭梯图(closed-end muti-ladders)在射影平面上的嵌入个数.3.设(G,u,v)是以u和v为根的双根连通图,用边e连接根u和c,所得之图记为G+e. Gross(?)寸根u和c的度均为2的情形,给出了G+e的亏格分布与(G,u,v)的部分亏格分布之间的一个关系.本文第四章,我们在条件上进行了推广,将其中一个根的度推广到任意大的情形,划分依据进行了改进,并由(G,u,v)的部分亏格分布导出了G+e的亏格分布.4.图G的最大亏格γM(G)有上界[β(G)/2],其中β(G)为G的Betti数,若γM(G)=[β(G)/2],则称G是上可嵌入的.任韩等人在文[J. East China Normal University (Natural Science),5(2010),1-13]中,全面阐述了近30年来关于图的最大亏格及其相关问题所取得的进展,并提出了如下两个猜想：(1)设G为简单连通图,且G的每条边含在一个三角形K3中,则G是上可嵌入的：(2)设c为任意的正数,则存在一个目然数N(c),使得对每一个图G.若G的点数n≥N(C),且最小度δ(G)≥cn,则G是上可嵌入的.本文第五章,我们否定了上述两个猜想,并探讨了上述猜想成立的条件.5.令Km,m,m(m≥1)是一个完全正则三部图,G是一个围长大于4的二部图,且G的最大度Δ(G)≤2m.本文第六章,我们应用White-Pisanski理论,计算了笛卡尔积图Km,m,m×G的亏格,并类似得到了Km.m.m与一些非二部图的笛卡尔积的交叉帽数.6.设Gm和Gn分别表示有m个点和n个点的两个不交的圈,Cm+Gn表示Cm与Cn的联图.本文第七章,得到当m>3且n>3或m=n=3时,Gm+Gn的亏格为[(m-2)(n-2)/4],其交叉帽数为[(m-2)(n-2)/2].更多还原

【Abstract】 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].更多还原