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 条
[21]   Complete bipartite graphs flexible in the plane [J].
Kovalev, M. D. ;
Orevkov, S. Yu. .
SBORNIK MATHEMATICS, 2023, 214 (10) :1390-1414
[22]   Multicolored forests in complete bipartite graphs [J].
Brualdi, RA ;
Hollingsworth, S .
DISCRETE MATHEMATICS, 2001, 240 (1-3) :239-245
[23]   Embedding Complete Bipartite Graphs into Wheel Related Graphs [J].
Greeni, A. Berin ;
Joshwa, P. Leo .
JOURNAL OF ADVANCED COMPUTATIONAL INTELLIGENCE AND INTELLIGENT INFORMATICS, 2023, 27 (04) :645-648
[24]   Crossing numbers of complete bipartite graphs [J].
Balogh, Jozsef ;
Lidicky, Bernard ;
Norin, Sergey ;
Pfender, Florian ;
Salazar, Gelasio ;
Spiro, Sam .
XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 :78-87
[25]   Terminal-pairability in complete bipartite graphs with non-bipartite demands Edge-disjoint paths in complete bipartite graphs [J].
Colucci, Lucas ;
Erdos, Peter L. ;
Gyori, Ervin ;
Mezei, Tamas Robert .
THEORETICAL COMPUTER SCIENCE, 2019, 775 :16-25
[26]   Bounding the tripartite-circle crossing number of complete tripartite graphs [J].
Camacho, Charles ;
Fernandez-Merchant, Silvia ;
Milutinovic, Marija Jelie ;
Kirsch, Rachel ;
Kleist, Linda ;
Matson, Elizabeth B. ;
White, Jennifer .
JOURNAL OF GRAPH THEORY, 2022, 100 (01) :5-27
[27]   The equitable vertex arboricity of complete tripartite graphs [J].
Guo, Zhiwei ;
Zhao, Haixing ;
Mao, Yaping .
INFORMATION PROCESSING LETTERS, 2015, 115 (12) :977-982
[28]   On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs [J].
Gethner, Ellen ;
Hogben, Leslie ;
Lidicky, Bernard ;
Pfender, Florian ;
Ruiz, Amanda ;
Young, Michael .
JOURNAL OF GRAPH THEORY, 2017, 84 (04) :552-565
[29]   A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs [J].
Liu, RY ;
Zhao, HX ;
Ye, CF .
DISCRETE MATHEMATICS, 2004, 289 (1-3) :175-179
[30]   A Study of Anti-Magic Graphs on Corona Product of Complete Graphs and Complete Bipartite Graphs [J].
Muya, James Githinji ;
Shobhalatha, G. .
COMMUNICATIONS IN MATHEMATICS AND APPLICATIONS, 2022, 13 (05) :1337-1345
12345