若干典型图类的交叉数及其相关问题研究

The problem of crossing number of a graph originated from a practical application, whose theory has been widely applied in many fields, such as the design of electronic circuits, the identification and repaint of sketch, and the graphical representation of DNA in biology engineering. However, it has been proven that computing the crossing number of a graph is NP-complete. Because of its difficulty, the exact values of crossing numbers are known only for few families of graphs at present，and even the crossing numbers of the complete graph and the complete bipartite graph are still open problems. And there is not a complete theoretical system for the crossing number of a graph. In this project, with some new methods, the crossing numbers of some typical classes of graphs, such as the complete bipartite graph and the complete multipartite graph、the Cartesian product of the complete graph with path as well as cycle with cycle, are investigated. In addition, we also study the general theory of the crossing number of a graph, and strive to reveal the relationships of the crossing number between Cartesian product of graphs and its factor graphs, and characterize the internal relations between the crossing number of a graph and its characteristic structure as well as other parameters, and try to solve or partly solve the interpolation conjecture on the crossing number of 3-regular graph. It has important theoretical significances and practical values to study these problems.

图的交叉数问题起源于一个实际应用问题，其理论在电路板设计、草图识别与重画以及生物工程DNA的图示等领域有着广泛应用。然而，已经证明确定图的交叉数是NP-完全问题。由于其难度大，目前能够确定其交叉数的图类非常少，甚至完全图和完全2-部图等典型图类的交叉数都尚未被完全确定。而且在图的交叉数问题研究上，目前也尚未形成一套完整的理论体系。本项目，一方面尝试用新的方法研究一些典型图类的交叉数，包括完全2-部图以及完全多部图、完全图与路的笛卡尔积图、圈与圈的笛卡尔积图；另一方面，对图的交叉数的一般性理论展开研究，试图揭示笛卡尔积图与其因子图之间的交叉数关系，刻画图的交叉数与图的特征结构以及其它参数之间的内在联系，力争解决或部分解决3-正则图的交叉数插值猜想。这些问题的研究不仅有重要的理论意义而且还有广泛的实际应用价值。

图的交叉数是拓扑图论研究中的一个重要问题，其具有重要的理论意义和现实意义，但从计算难度上，确定图的交叉数是一个NP-难问题。本项目不仅研究了若干重要图类的交叉数，同时对交叉数的一般性理论展开了深入研究，发展和发现了一些新的研究方法，得到了一些交叉数的新性质。项目研究的重要结果包括：（1）得到了完全2-部图K_{7,n}和完全3-部图K_{3,3,n}的交叉数的较好的下界，为最终确定其交叉数奠定了基础；（2）确定了K_{m}□P_n、K_{1,1,m}□P_n、K_{2,2,2}□S_n等若干笛卡尔积图的交叉数，得到了一些新的研究方法，这些方法可用于确定更多笛卡尔积图的交叉数；（3）得到了更为一般性的带帽笛卡尔积图的交叉数的下界公式，揭示了笛卡尔积图与因子图之间的交叉数关系，推广了Bokal等人的有关结果；（4）实质性地改进了Klesc-收缩手术，提出了多个新的收缩技巧，为进一步研究星图的笛卡尔积图的交叉数提供借鉴；（5）刻画了cr(G_1□G_2)=k以及cr(G_1+G_2)=k的图的结构特征，为进一步刻画一般的图 （交叉数为给定值）的子式结构特征，积累了宝贵的经验和方法。. 项目研究的结果进一步完善了交叉数的理论体系，为继续确定许多重要图类的交叉数提供了重要的理论支持。项目研究成果包括：发表在《Discrete Mathematics》《中国科学:数学》等期刊上的13篇论文，以及正在审稿的4篇论文；培养硕士研究生5名、博士研究生1名。圆满完成了项目原计划的成果目标。