图的亏格嵌入问题研究

The embedding of a graph on a surface is a major theme of topological graph theory, and the minimum genus problem is NP-complete. So far, for certain special classes of graphs only with good symmetry, formula for their genera have been given. The methods used mainly involve quotient embeddings that are formed as voltage or current in the dual case. To some extent, this method shows a limitation to deal with the minimum genus of other graph, especially, the classes of graphs with weak symmetry. However, on the basis of joint tree, the corresponding relation is established between the joint trees and the embeddings.So the topological graph problem for enumerating the minimum genus of a graph is transformed into a combinatorial problem for counting the minimum genus of associated surface. As for the minimum genus problem, the extendability and priority of joint tree have been appeared sharply in the results which we have achieved. Using this idea in study of minimum genus problem is a frontier as well as innovative subject. The realization of the research plan will facilitate the exploration of the embeddability of graphs.

图在曲面上的嵌入是拓扑图论的主要问题，其中，图的最小亏格问题是NP-困难的。为此，目前已解决最小亏格问题的图类主要具有较好的对称性，且此方法对解决其它图类，特别是对称性比较弱的图类的最小亏格问题有很大的局限性。申请人旨在利用联树模型，建立联树和嵌入的一一对应关系，把求图的最小亏格的拓扑图论问题转化为求具有最小亏格的关联曲面的组合问题。进而将通过刻画具有最小亏格的关联曲面的特性来解决更广泛图类的亏格问题。关于最小亏格问题，目前已经取得的结果已经显现出此联树法具有一定的优越性和推广性。用此思想研究图的最小亏格问题是一个前沿性的创新课题，本研究计划的如期实现期望有助于推进图的可嵌入性问题的研究进程。

图在曲面上的嵌入是拓扑图论的主要问题。其中，图的最小亏格问题是NP-困难的。目前已解决的最小亏格的图类主要具有很好的对称性。本项目利用联树模型，建立了联树和嵌入的一一对应关系，把求最小亏格的拓扑图论的问题转化为求具有最小亏格的关联曲面的组合问题。 得到了一类边合并图的最小亏格，两类二部图与一个点suspensions图及两类apex图的最小亏格。进一步得到完全二部图最小亏格以及最小亏格嵌入数目问题。实际上，其求解过程提供了计算此类图最小亏格的一种算法。由此知，计算此类图的最小亏格是一个用线性时间算法可以实现的问题。另外，还研究了Welded纽结解结数问题，项目组成员利用 warping 度的方法得到一个 welded 纽结的解结数的一个上界, 比 S. Satoh 得到的上界要小。研究了一类特殊welded纽结的基本群结构。研究了平面图的线性2-荫度，得到了若干平面图线性2-荫度。还研究了邻和可区别全染色问题，运用组合零点定理和反证法讨论了d-退化图的邻和可区别全可选性问题，给出了此类图的邻和可区别全可选性的一个上界，同时研究了最大度较小的图的邻和可区别全可选性，得到了其满足全染色猜想的一个充分条件；针对一般平面图研究了其邻和可区别全染色，得到了最大度限制条件下平面图邻和可区别全染色的上界；研究了一类稀疏图的邻和可区别全染色问题，得到了此类稀疏图满足全染色猜想的一个 充分条件；研究了Halin图的邻和可区别全染色，得到了Halin图的邻和可区别全色数。课题的研究具有重要的理论意义和广泛的应用前景，比如可应用于印刷板或集成电路布线问题，为计算机网络设计提供理论依据等，也丰富了图的染色理论。