基于结构图论的一般图嵌入分布的研究

项目名称： 基于结构图论的一般图嵌入分布的研究

项目编号： No.11471106

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 陈仪朝

作者单位： 湖南大学

项目金额： 63万元

中文摘要： 图的嵌入分布是全面刻画图在曲面上嵌入的一个拓扑不变量、是当代拓扑图论最活跃的研究课题之一。以往结果多侧重于研究低亏格曲面的上图的嵌入计算及一些特殊图类的嵌入分布，较少涉及一般图类的嵌入分布。本项目在我们前期工作已获得一般3-正则外平面图(树宽为2)及一般3-正则Halin图（树宽为3）的嵌入分布的基础上， 基于Robertson 与Seymour所发展起来的结构图理论，运用树分解、矩阵理论，曲面组合学理论，对称函数理论、有限群表示理论等组合、分析、代数及拓扑方法，发展新的运算等研究下述问题：（I）树宽为2的图的嵌入分布；（II）树宽为3的图的嵌入分布；(III) 给定树宽图的嵌入分布；(IV) 有向图的嵌入分布。积极的结果将得到这些图类的嵌入分布的精确值与渐近值，研究结果除将进一步丰富曲面组合学外、也将进一步加深分析、代数等工具在拓扑图论中的交叉应用。

中文关键词： 图；有向图；树宽；嵌入分布

英文摘要： The embedding distribution of graphs and the enumeration of rooted maps are two equivalent problems of the enumeration theory on graphs embedding into surfaces. It is a topological invariant of a graph into a surface and an active research area in modern topological graph theory. Known from the published literatures, most results were related to the enumeration of embeddings of graphs into surfaces with lower genus and the embedding distribution of some special classes of graphs. We have already derived recurrence formula for 3-regular outerplanar graphs and known that outerplanar graphs are of tree-width 2. Moreover, we have a formula for genus distributions of fan graphs, which are outerplanar graphs with a single vertex of high valence. Our research plan is seek to develop some new methods to investigate the embedding distributions all bounded tree-width graphs by applying tree decomposition and topological methods, which methods will mainly base on such some theories as the structure theory presented by Robertson and Seymour, overlap matrix , joint tree theory , characters of symmetric groups and so on. We also develop method to study genus distribution of a digraph. A positive solution would be a polynomial-time algorithm for exact values or reasonably tight approximations. A negative solution would be proof that the problem is NP-hard. Besides, employing the enumerating theory on rooted maps and the algebraic representation of the map presented by Tutte, we systematically investigate the nonorientable embedding distribution on the graph of high valence by extending orientable permutation partitions.

英文关键词： Graph;Digraph;Tree width;Embedding distribution