ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K1,8,n

数学物理学报

ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_1,8,n

黄元秋; 赵霆雷

湖南师范大学数学系, 长沙 410081

收稿日期:2005-06-28 修回日期:1900-01-01 出版日期:2006-12-25 发布日期:2006-12-25
通讯作者: 黄元秋
基金资助:
This work is supported by the Key Project of the Education Department of Hunan Province of China (05A037) and by Scientific Research Fund of Hunan Provincial Education Department (06C515).

ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_1,8,n

Huang Yuanqiu; Zhao Tinglei

Department of Mathematics, Hunan Normal University, Changsha 410081, China

Received:2005-06-28 Revised:1900-01-01 Online:2006-12-25 Published:2006-12-25
Contact: Huang Yuanqiu

摘要/Abstract

摘要： The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph K_m,n (m≤ n) is Z(m,n), where Z(m,n)=\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor$$\lfloor\frac{n-1}{2}\rfloor$ (for any real number x, $\lfloor x\rfloor$ 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 K_1,8,n is $Z(9, n)+ 12\lfloor\frac{n}{2}\rfloor$.

关键词: Graphs, Drawing, Crossing number, Complete tripartite graph, Complete tripartite graph

Abstract: The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph K_m,n (m≤ n) is Z(m,n), where Z(m,n)=\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor$$\lfloor\frac{n-1}{2}\rfloor$ (for any real number x, $\lfloor x\rfloor$ 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 K_1,8,n is $Z(9, n)+ 12\lfloor\frac{n}{2}\rfloor$.

Key words: Graphs, Drawing, Crossing number, Complete tripartite graph, Complete tripartite graph

中图分类号:

05C10

黄元秋; 赵霆雷. ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_1,8,n[J]. 数学物理学报, 2006, 26(6): 1115-.

Huang Yuanqiu; Zhao Tinglei. ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_1,8,n[J]. Acta mathematica scientia,Series A, 2006, 26(6): 1115-.

ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_1,8,n

ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K_1,8,n

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

Metrics

本文评价

推荐阅读 10