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

被引：5

作者：

Chen, Yichao ^{[1
]}

Yang, Yan ^{[2
]}

机构：

[1] Hunan Univ, Coll Math & Econometr, Changsha 410082, Hunan, Peoples R China

[2] Tianjin Univ, Dept Math, Tianjin 300072, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2017年 / 34卷 / 01期

关键词：

Thickness; Complete multipartite graph; Join;

D O I：

10.1007/s10878-016-0057-1

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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

页数：9

共 9 条

[1] THICKNESS OF AN ARBITRARY COMPLETE GRAPH [J].

ALEKSEEV, VB ;

GONCAKOV, VS .

MATHEMATICS OF THE USSR-SBORNIK, 1976, 30 (02) :187-202

[2] THICKNESS OF COMPLETE GRAPH [J].

BEINEKE, LW ;

HARARY, F .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (06) :850-&

[3]

BEINEKE LW, 1964, P CAMB PHILOS SOC, V60, P1

[4] DETERMINING THE THICKNESS OF GRAPHS IS NP-HARD [J].

MANSFIELD, A .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1983, 93 (JAN) :9-23

[5] The thickness of graphs: A survey [J].

Mutzel, P ;

Odenthal, T ;

Scharbrodt, M .

GRAPHS AND COMBINATORICS, 1998, 14 (01) :59-73

[6] A simulated annealing algorithm for determining the thickness of a graph [J].

Poranen, T .

INFORMATION SCIENCES, 2005, 172 (1-2) :155-172

[7]

TUTTE WT, 1963, INDAG MATH, V25, P567

[8]

VASAK JM, 1976, NOT AM MATH SOC, V23, pA479

[9]

Yang Y, 2014, ARS COMBINATORIA, V117, P349

← 1 →