近完全二部图的交叉数  

The Crossing Number of Nearly Complete Bipartite Graphs

作　　者：王雨溪 吕胜祥 张湘林 Yu Xi WANG;Sheng Xiang LV;Xiang Lin ZHANG(School of Mathematics and Statistics,Hunan University of Finance and Economics,Changsha410205,P.R.China)

机构地区：[1]湖南财政经济学院数学与统计学院,长沙410205

出　　处：《数学学报（中文版）》2023年第6期1147-1166,共20页Acta Mathematica Sinica：Chinese Series

基　　金：湖南省教育厅科学研究项目(19C0318);湖南省教育厅科学研究重点项目(21A0590,20A079);湖南省自然科学基金面上项目(2019JJ40080,2021JJ30067)。

摘　　要：图G的交叉数是刻画图的非平面性的一个重要参数.它是指图G在平面上的所有画法中边与边之间交叉数目的最小值.确定具体图类的交叉数是图的交叉数问题中一个经典的研究方向.Zarankiewicz于1954年提出了完全二部图交叉数的猜想:cr(Km,n)=[2/m][2/m-1][2/n][2/n-1].1971年,Kleitman证明了当min{m,n}≤6时,上式成立.由于其难度,完全二部图交叉数的研究进展是较缓慢的.至今,完全二部图K_(7,n)(n≥11)的交叉数都还未确定.然而,我们发现研究近完全二部图的交叉数可了解在完全二部图中加边与完全二部图交叉数的增长程度之间的关系.因此,为了促进完全二部图交叉数的研究,本文借助旋系与交叉数之间的关系、图的结构性质以及图的顶点度局部修改法确定了五个近完全二部图的交叉数.The crossing number of graph G is an important parameter to describe the nonplanarity of graph.It is the minimum number of edges crossed among all the drawings of G on the plane.Determining the crossing number of graphs is a classical research direction.It was put forward by Zarankiewicz in 1954 thatcr(Km,n)=[2/m][2/m-1][2/n][2/n-1].This conjecture has been verified by Kleitman in 1971 for min{m,n}≤6.The research of cr(K(m,n))is relatively slow due to its difficulty.So far,the crossing number of K_(7,n)(n≥11)is still an open problem.However,studying the crossing number of nearly complete bipartite graphs helps to understand the effect of adding edges to the complete bipartite graph on its crossing number.Therefore,in order to promote the research on the crossing number of complete bipartite graphs,this paper determines the crossing number of five nearly complete bipartite graphs by means of the rotation,the structural properties of the graphs and"local vertex's degree modification".

关 键 词：画法 交叉数 联图 旋系 完全二部图 

分 类 号：O157.5[理学—数学]