图类的亏格与嵌入分布及其相关问题研究

Topological graph theory is an important branch of graph theory. To determine the genus and the embedding distribution of a graph are NP-hard, as well the classic and key problems in topological graph theory, which have attracted the attention and study of many well known international scholars. Not only combine the traditional methods, we will also utilize the embedding methods of Joint-Tree Model which are recently introduced by Professor Liu Yanpei and find some new combinatorial methods to determine the genus and the embedding distribution of some families of classical graphs; to estimate the number of embedding on special surface of graphs; to study some properties on the distribution of roots of embedding polynomials by using theories and methods of polynomials in algebra; to study polynomial-time algorithm of the genus and the embedding distribution for some families of special graphs; and to study the unimodal conjecture of graph embedding distribution. Some of the research contents in this proposal are the deepening and expantion of our preliminary results (such as the research on the number of the maximum genus embedding of graph), some are classic problems in topological graph theory (eg, to determine the genus and the embedding distribution of graphs), and some others are famous conjectures and new problems from international academic journals (such as the Gross conjecture, the genus expansion problems for the joint graph). The contents involve the field of science including algebra、surface topology group algorithm theory and so on.Solving these problems will greatly enrich and improve the topological graph theory, and promote the development of the topological graph theory and its related disciplines as well。

拓扑图论是图论学科的重要分支。确定图的亏格和嵌入分布均是NP-难问题，但又是拓扑图论中的经典和核心问题，引起了国际上许多知名学者的重视和研究。本项目既结合传统的方法，又运用刘彦佩提出的联树模型法以及发现新的组合方法，确定一些经典图类的亏格及嵌入分布；给出图在特定嵌入下的嵌入数目估计；借助代数学中的多项式理论与方法，研究图的嵌入多项式的根的分布性质；研究求一些特殊图类的亏格及嵌入分布的多项式时间算法；同时开展图的嵌入分布单峰猜想研究。项目研究的内容，有的是我们前期研究结果的深化和拓展（如最大亏格嵌入个数研究）,有的是经典问题（如确定图的亏格及嵌入分布），有的是国际重要学术刊物上提出的著名猜想或新问题（如Gross猜想、联图亏格扩展问题）。内容涉及到代数学、曲面拓扑学、群论、算法理论等领域。问题的解决，不仅极大地丰富和完善拓扑图论中的相关内容，同时也将有力地推动拓扑图论及促进相关学科的发展。

本项目主要研究图类的亏格与嵌入分布及其相关问题, 包括确定一些特殊图类的亏格、有向图和无向图的嵌入分布、图的厚度和地图计数、以及图的交叉数。所得结果进一步丰富和完善拓扑图论中的相关内容，促进拓扑图论发展具有重要意义。我们确定一类5-正则外平面图、双极图D3与路Pn的 笛卡尔积图的嵌入分布；得到了循环图C（2n+1,2）在射影平面上的嵌入个数；给出了一个双根图在其中一个根点的度为任意大的情形下根点自沾合图的亏格分布。确定了4-正则外平面有向图的有向亏格分布，同时证明其分布具有单峰性，也给出了类似无向图的劈分嵌入定理。证明了每一个整数n≥1，存在一个Petersen 图的幂图 Pn 的亏格与欧拉亏格为n，从进一步拓广或改进了Mohar与Vodopivec的结果。得到了极大平面地图,不可分离平面地图,三正则平面地图和平面树地图、单近4-正则地图和简单欧拉可平面地图计数表达式。获得了笛卡尔积图的厚度的上下界，且确定了笛卡尔积图Kn,n□Kn,n 的厚度。确定了完全3-部图K1,1,m 与路Pn的交叉数。 得到了一些新的联图的交叉数，包括一些不联通6点图与n个孤立点、与路、与圈的交叉数、K2,2,2,n与星图Sn。. 本项目发表论文29篇，其中SCI论文11篇，有的论文发表在《中国科学》、《Discrete Math.》、《Eurpean J.Combin.》、《Ars Combinatorics》等刊物上。另外,还有录用SCI论文4篇，在审论文5篇。