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

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: There is a linear algorithm to compute the maximum genus of a cubic graph. We pay attention to this conjecture. Unlike the maximum genus, the minimum genus is difficult to compute. It is known that to compute the minimum genus of a graph is NP-hard. We will calculate the minimum genus of some cubic graphs. Besides that, the total genus distribution(the strong total genus distribution) of some special cubic graphs will be investigated in this project too. As the application of embedding theory, we move on to the decycling number of a graph whose determination is a hard task. The decycling number has a wide application in computer theory. The main contents relating to decycling number involve the connection of Xuong tree and decycling number, determination of the decycling number of regular graphs or planar graphs.

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

本项目对三正则的嵌入性质及其应用进行了研究。项目的重要结果之一是对图的消圈数的研究，区别于以往从组合角度的研究，我们得到了从拓扑角度来刻画的结果。与刻画图的嵌入相类似，Xuong树在图的消圈数的刻画中也可以起到很重要的作用。另一方面，我们得到了图的以化学指标的研究。最后，我们还对三正则的顶点特殊划分进行了研究。