The thickness of the complete multipartite graphs and the join of graphs

被引：0

作者：

Yichao Chen

Yan Yang

机构：

[1] Hunan University,College of Mathematics and Econometrics

[2] Tianjin University,Department of Mathematics

来源：

Journal of Combinatorial Optimization | 2017年 / 34卷

关键词：

Thickness; Complete multipartite graph; Join; 05C10;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is known for relatively few classes of graphs, compared to other topological invariants, e.g., genus and crossing number. For the complete bipartite graphs, Beineke et al. (Proc Camb Philos Soc 60:1–5, 1964) gave the answer for most graphs in this family in 1964. In this paper, we derive formulas and bounds for the thickness of some complete k-partite graphs. And some properties for the thickness for the join of two graphs are also obtained.

引用

页码：194 / 202

页数：8

共 15 条

[1]

Alekseev VB(1976)The thickness of an arbitrary complete graph Math Sbornik 30 187-202

[2]

Gončhakov VS(1965)The thickness of the complete graph Can J Math 17 850-859

[3]

Beineke LW(1964)On the thickness of the complete bipartite graph Proc Camb Philos Soc 60 1-5

[4]

Harary F(1983)Determining the thickness of graphs is NP-hard Math Proc Camb Philos Soc 93 9-23

[5]

Beineke LW(1998)The thickness of graphs: a survey Graph Combin 14 59-73

[6]

Harary F(2005)A simulated annealing algorithm for determining the thickness of a graph Inf Sci 172 155-172

[7]

Moon JW(1963)The thickness of a graph Indag Math 25 567-577

[8]

Mansfield A(1976)The thickness of the complete graph Not Am Math Soc 23 A-479-351

[9]

Mutzel P(2014)A note on the thickness of Ars Comb 117 349-undefined

[10]

Odenthal T(undefined)undefined undefined undefined undefined-undefined

← 1 2 →