三正则图的嵌入性质及其应用

项目名称： 三正则图的嵌入性质及其应用

项目编号： No.11401576

项目类型： 青年科学基金项目

立项/批准年度： 2014

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

项目作者： 魏二玲

作者单位： 中国人民大学

项目金额： 22万元

中文摘要： 三正则图是非常重要的一类图。本项目拟对三正则图的曲面嵌入理论及其应用进行研究。我们已知图的最大亏格的计算存在多项式算法，但限制在三正则图上，刘彦佩曾提出猜想：三正则图的最大亏格的计算存在线性算法。本项目拟对这个问题进行研究。对应于最小亏格，问题难度增加，因为图的最小亏格的计算是NP困难的。本项目拟对具有特殊结构，对称性比较强的三正则图，计算其最小亏格，丰富最小亏格领域的研究内容。对对称性强的三正则图，计算其亏格分布，强亏格分布。在理论研究的基础之上，应用图的曲面嵌入理论，拟对图的消圈数进行探讨。消圈数在计算机理论中有重要的实际意义。我们将研究Xuong树与消圈数之间的关系，以及正则图，平面图的消圈数的显性求解，推动消圈数问题的研究。这些结果大大超越了目前这方面的已有结果。

中文关键词： 3正则图；消圈数；嵌入；；

英文摘要： Cubic graphs have been extensively studied. We focus on the embedding theory of cubic graphs in this project. It is well known that the maximum genus of a graph can be solved in a polynomial algorithm. But to cubic graphs, Liu ever proposed a Conjecture:

英文关键词： cubic graph；decycling number；embedding；；