摘要
The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤G. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K1,8,n is Z(9, n) + 12[n/2].
The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m ≤ n) is Z(m,n), where Z(m,n) = [m/2][m-1/2][n/2] (for any real number x, [x] denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m ≤ 6. In this article, the authors prove that if Zarankiewicz' conjecture holds for m ≤ 9, then the crossing number of the complete tripartite graph K1,8,n is Z(9, n) + 12[n/2].
出处
《数学物理学报(A辑)》
CSCD
北大核心
2006年第B12期1115-1122,共8页
Acta Mathematica Scientia
基金
This work is supported by the Key Project of the Education Department of Hunan Province of China (05A037)by Scientific Research Fund of Hunan Provincial Education Department (06C515).
关键词
图论
完备三重图
相交数
双向图
Graphs
Drawing
Crossing number
Complete tripartite graph
Complete tripartite graph