Rotation and Crossing Numbers for Join Products

被引：4

作者：

Ding, Zongpeng ^{[1
]}

机构：

[1] Hunan First Normal Univ, Dept Math, Changsha 410205, Hunan, Peoples R China

来源：

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY | 2020年 / 43卷 / 06期

基金：

中国国家自然科学基金;

关键词：

Rotation; Disconnected graph; Crossing number; Join product; Drawing; GRAPHS;

D O I：

10.1007/s40840-020-00916-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Computing the crossing number of a graph is NP-hard. In the paper, for a disconnected 6-vertex graph Q=C-5 boolean OR K-1, we obtain the crossing number Z(6,n) + left perpendicularn/2right perpendicular of the graph Q(n) which is the join product of Q with the discrete graph by introducing the "rotation" method. Moreover, we give crossing numbers for join products of Q with the path and the cycle. Besides, we also get directly crossing numbers for join products of some connected 6-vertex graphs with the path and the cycle, some of which were studied by M. Klesc, D. Kravecova, and J. Petrillova.

引用

页码：4183 / 4196

页数：14

共 14 条

[1] A FRAMEWORK FOR SOLVING VLSI GRAPH LAYOUT PROBLEMS [J].

BHATT, SN ;

LEIGHTON, FT .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1984, 28 (02) :300-343

[2] ADDING ONE EDGE TO PLANAR GRAPHS MAKES CROSSING NUMBER AND 1-PLANARITY HARD [J].

Cabello, Sergio ;

Mohar, Bojan .

SIAM JOURNAL ON COMPUTING, 2013, 42 (05) :1803-1829

[3] Zarankiewicz's Conjecture is finite for each fixed m [J].

Christian, Robin ;

Richter, R. Bruce ;

Salazar, Gelasio .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (02) :237-247

[4]

Clancy K., 2019, ARXIV190105155

[5] THE CROSSING NUMBERS OF JOIN OF SOME GRAPHS WITH n ISOLATED VERTICES [J].

Ding, Zongpeng ;

Huang, Yuanqiu .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2018, 38 (04) :899-909

[6] CROSSING NUMBER IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (03) :312-316

[7] Orthogonal drawings and crossing numbers of the Kronecker product of two cycles [J].

Jha, Pranava K. ;

Devisetty, Savitri .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2012, 72 (02) :195-204

[8]

Kleitman D. J., 1970, Journal of Combinatorial Theory, Series A, V9, P315, DOI 10.1016/S0021-9800(70)80087-4

[9]

Kles M., 2011, Electr. Eng. Inform., V2, P522

[10]

Klesc M., 2007, Electron. Notes Discrete Math, V28, P349

← 1 2 →