【作者】 邹谦；

【导师】 曹金明；

【作者基本信息】 湖南大学 ， 计算数学， 2010， 硕士

【摘要】 已知一个连通图G和一个闭曲面S(无边缘的紧2-维流形),若存在一个1-1连续映射h：G→S,使得S-h(G)的每个连通分支均是一个2-胞腔,则称G在S上有一个胞腔嵌入。若曲面S是可定向的,则嵌入是可定向嵌入；若曲面S是不可定向的,则嵌入是不可定向嵌入。图G在曲面S上的两个嵌入h：G→S和g：G→S是等价的当且仅当存在一个同胚f：S→S使得fοh=g.图的曲面嵌入问题是拓扑图论的一个重要的研究分支,它主要是研究图的可嵌入理论和嵌入计数理论。每一个图都可以嵌入到某个曲面上,使得一个图G可以嵌入到亏格为k的曲面Sk的最小非负正整数k称为是G的亏格。那么图在各种不同亏格的曲面上各有多少个不等价的嵌入呢?这就是图的嵌入亏格分布问题。图在曲面上的嵌入分布作为拓扑图论的一个重要研究问题,目前为止所得结果仍然很少。对它的研究的方法从如下方面开展：对于一些具有对称性的图,根据旋与嵌入的对应关式,对其循环置换群的圈结构的分解进行计数；基于Ringle-White加边的组合拓扑方法；Mohar B提出的覆盖矩阵以及近年来的刘彦佩教授提出的嵌入的联树模型。总体而言,每种方法解决某些图的嵌入亏格分布都有一定的局限性。另外,组合序列的(强)单峰性一直组合数学家关注的一个课题。迄今为止,图的可定向嵌入分布序列的(强)单峰性对已知的几类图是成立的。图的不可定向嵌入分布序列的(强)单峰性还没有类似的结果。总之,图的(不)可定向嵌入分布序列的(强)单峰性猜想至今还是一个谜。此外,单峰点的位置的求解也是一个热门的研究方向。在本论文中,我们首先根据Chebyshev第二类多项式的性质,得到了一类含有两个参数的齐次和非齐次的递推关系的解的解析式。其次,我们利用B.Mohar的覆盖矩阵方法,得到了Closed-end ladders和Cobblestone path两类图的精确的可定向亏格分布和完全亏格分布表达式；再者,对于任意的自然数对(r,s),通过程序计算,我们发现(r,s)型necklaces不可定向亏格分布是单峰的,并且猜测了它的单峰点的具体位置。进一步研究,我们发现其单峰点位置与图的平均亏格之间存在一定的联系,于是我们提出了一个关于单峰点与平均亏格的猜想。更多还原

【Abstract】 Given a connected graph G and a surface S(a compact closed 2-dimensional manifold without boundary), if there exists a homeomorphism h:G→S, such that each connected component of S→h(G) is a 2-cell, then h(G) is an embedding (in early reference called 2-cell embedding)on S. If S is orientable, then the embed-ding is orientable; else if S is nonorientable, then the embedding is non-orientable. Two embeddings h:G→S and g:G→S of G on a surface S are said to be equivalent if there is a homeomorphism f:S→S, such that f(?)h=g. The embedding theory of graph is one of the most important branches in topological graph theory and it studies mainly on embeddability and counting theory.Each graph can be embedded onto some surface and the genus of a graph G is the smallest non-positive integer k, such that G can be embedded on the surface Sk with the genus k. Then how many distinct embeddings dose a graph have on surfaces with different genus? This is the problem of embedding genus distribution for a graph.The classification for the graph embedding onto the surface is an important research direction of the topological graph, the results obtained in such field are still very few and the research techniques are mainly as follows:the combinatorial enumeration formulae of Jackson D.M;the topological method by adding edges; the overlap-matrix method by Mohar.B and the joint tree model introduced by Y.P.Liu recently. On the whole, each method has its limitation to study the embedding distribution for the embedding of some class of graph.In addition, the (strongly) unimodal enumerative sequence is a hot topic stud-ied by the combinatorists. Up to now, the (strong) unimodality of the orientable embedding distribution for some known graph has been verified, whereas there is still not any similar result for the non-orientable embedding distribution. On the whole, the conjecture that the embedding sequence is (strongly)unimodal is still a riddle. In addition, the solution of the mode is also a hot research field.In this thesis, firstly, by the property of the Chebyshev polynomials of the second kind, we obtain the solutions for a class of constant coefficient homogeneous and non-homogenous recurrence relations with two indices; Secondly, using the overlap-matrix method, we obtain the explicit formulaes of the orientable and the total embedding distribution for the two classes of graphs:Closed-end ladders and Cobblestone path. Furthermore, by computation, we verify the unimodality for’ the non-orientable embedding distribution for the (r,s) necklaces and derive the mode of it. By further study, we discover that there exists some relation between the mode and the average genus for such graph embedding, which makes us to pose one conjecture on the relation for the mode and the average genus in general case.更多还原