符号图在曲面上的准亏格与最大准亏格

The orientation embedding of signed graphs on surfaces is a latest research direction of topological graph theory. Following a series of problems and conjectures putted forward by Zaslavsky,Siran and Archdeacon,etc., the demigenus and maximum demigenus of signed graphs on surfaces is investigated in this project. The research contents of this project mainly involves: studying the demigenus additivity of the union of signed graphs; calculating the demigenus of some signed graphs of complete graphs and complete bipartite graphs,etc.; determining the largest demigenus or upper bound over all singed graphs of complete graphs and complete bipartite graphs,etc.; obtaining the lower bound on maximum demigenus of signed graphs; characterizing the single face orientation embeddability of signed graphs; describing the Betti-deficiency stability of signed graphs; constructing effective algorithms for maximum demigenus orientation embedding; establishing an interpolation theorem for the surfaces on which the signed graphs can be orientation embedded.

符号图在曲面上的定向嵌入是拓扑图论的最新研究方向之一。基于Zaslavsky、Siran、Archdeacon等提出的系列科学问题与猜想，本项目将对符号图定向嵌入到曲面上的准亏格与最大准亏格展开研究，主要内容包括：研究符号图并图的准亏格可加性；计算完全图、完全二部图等典型图类的具体符号图的准亏格；确定完全图、完全二部图等典型图类的所有符号图准亏格的最大值或上界；给出符号图的最大准亏格下界；刻画符号图的可单面定向嵌入性；探索符号图的Betti-亏数稳定性；设计符号图最大准亏格定向嵌入有效算法；建立符号图可定向嵌入曲面插值定理。

符号图在曲面上的定向嵌入是拓扑图论的最新研究方向之一。本项目以Archdeacon提出的公开问题以及Thomas zaslavsky提出的关于±Kn的准亏格猜想为研究对象，确定了完全二部图K3,n与K4,n的所有符号图准亏格的最大值；发现了2-胞腔嵌入的一类加点构造方法，计算得出了完全二部图Kn,n与Kn,n+1去掉n条独立边后的最小可定向亏格；确定了当n=12s+3与n=12s+7时±Kn的准亏格，以及发现了当n取较小值时±Kn的电压图，为下一步研究n取其他值时奠定了基础；给出了直径为2或3的简单符号图的最大准亏格与上可嵌入性；得到了完全三部图K4mn,4mn,2n的最小可定向亏格；刻画了图的上可嵌入性充分条件与非上可嵌入3-正则图的扩充。