The Thickness of Some Complete Bipartite and Tripartite Graphs

被引：0
作者：
Hu, Si-wei [1 ]
Chen, Yi-chao [2 ]
机构：
[1] Yali Peicui Sch, Changsha 410021, Peoples R China
[2] Suzhou Univ Sci & Technol, Sch Math, Suzhou 215009, Peoples R China
来源：
ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES | 2024年 / 40卷 / 04期
关键词：
thickness; complete bipartite graph; complete tripartite graph; planar decomposition;
D O I：
10.1007/s10255-024-1128-1
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we obtain the thickness for some complete k partite graphs for k = 2; 3: We first compute the thickness of Kn;n+8 by giving a planar decomposition of K4k for k 3. Then, two planar decompositions for K1;g;g(g when g is even and for K 1;g; 1 2 (g when g is odd are obtained. Using a recursive construction, we also obtain the thickness for some complete tripartite graphs. The results here support the long-standing conjecture that the thickness of Km;n is. mn 2(m+n. for any positive integers m; n
引用
收藏
页码：1001 / 1014
页数：14
相关论文
共 50 条
[41]   Characterization of the Imbalance Problem on Complete Bipartite Graphs [J].
Ge, Steven ;
Itoh, Toshiya .
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2022, 2022, 13571 :55-66
[42]   Decomposition of complete bipartite graphs into paths and cycles [J].
Jeevadoss, S. ;
Muthusamy, A. .
DISCRETE MATHEMATICS, 2014, 331 :98-108
[43]   Nonorientable hamilton cycle embeddings of complete tripartite graphs [J].
Ellingham, M. N. ;
Schroeder, Justin Z. .
DISCRETE MATHEMATICS, 2012, 312 (11) :1911-1917
[44]   A Note on Chromatic Uniqueness of Certain Complete Tripartite Graphs [J].
Chen, Xiang'en ;
Su, Keyi ;
Yao, Bing .
ARS COMBINATORIA, 2012, 105 :205-211
[45]   The Edge Cover Chromatic Index of Complete Tripartite Graphs [J].
Wang, Meng ;
Xu, Changqing .
UTILITAS MATHEMATICA, 2012, 87 :279-283
[46]   On Interval Edge-colorings of Complete Tripartite Graphs [J].
Grzesik, Andrzej ;
Khachatrian, Hrant .
2013 COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES (CSIT), 2013,
[47]   Complete tripartite graphs arbitrarily decomposable into closed trails [J].
Horak, Mirko ;
Kockova, Zuzana .
GRAPHS '04, 2007, 36 :71-+
[48]   The thickness of the complete multipartite graphs and the join of graphs [J].
Yichao Chen ;
Yan Yang .
Journal of Combinatorial Optimization, 2017, 34 :194-202
[49]   The thickness of the complete multipartite graphs and the join of graphs [J].
Chen, Yichao ;
Yang, Yan .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (01) :194-202
[50]   THE THICKNESS OF SOME CARTESIAN PRODUCT GRAPHS [J].
Guo, Xia ;
Yang, Yan .
ARS COMBINATORIA, 2019, 147 :97-107
12345