On the crossing numbers of Cartesian products with paths

被引：41

作者：

Bokal, Drago ^{[1
]}

机构：

[1] Inst Math Phys & Mech, Dept Math, Ljubljana, Slovenia

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2007年 / 97卷 / 03期

关键词：

crossing number; Cartesian product; path;

D O I：

10.1016/j.jctb.2006.06.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Using a newly introduced operation on graphs and its counterpart on graph drawings, we prove the conjecture of Jendrol' and Scerbova from 1982 about the crossing number of the Cartesian product K-1,K-m 11 rectangle P-n. Our approach is applicable to the capped Cartesian products of P-n with any graph containing a dominating vertex. (c) 2006 Elsevier Inc. All rights reserved.

引用

页码：381 / 384

页数：4

共 10 条

[1] ON THE CROSSING NUMBERS OF PRODUCTS OF CYCLES AND GRAPHS OF ORDER 4
BEINEKE, LW
RINGEISEN, RD
[J]. JOURNAL OF GRAPH THEORY, 1980, 4 (02) : 145 - 155
[2] BOKAL D, 2006, THESIS U LJUBLJANA
[3] The crossing number of Cm x Cn is as conjectured for n≥m(m+1)
Glebsky, LY
Salazar, G
[J]. JOURNAL OF GRAPH THEORY, 2004, 47 (01) : 53 - 72
[4] JENDROL S, 1982, CASOPIS PRO PESTOVAN, V107, P225
[5] Kleitman D. J., 1970, Journal of Combinatorial Theory, Series A, V9, P315, DOI 10.1016/S0021-9800(70)80087-4
[6] The crossing number of K2,3 x C3
Klesc, M
[J]. DISCRETE MATHEMATICS, 2002, 251 (1-3) : 109 - 117
[7] KLESC M, 1991, MATH SLOVACA, V41, P113
[8] CROSSING NUMBER OF C3 X CN
RINGEISEN, RD
BEINEKE, LW
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 24 (02) : 134 - 136
[9] Infinite families of crossing-critical graphs with given average degree
Salazar, G
[J]. DISCRETE MATHEMATICS, 2003, 271 (1-3) : 343 - 350
[10] WHITE AT, 1978, SELECTED TOPICS GRAP, P15

← 1 →