On the crossing numbers of Cartesian products with paths

被引：42

作者：

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 [J].

BEINEKE, LW ;

RINGEISEN, RD .

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) [J].

Glebsky, LY ;

Salazar, G .

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 [J].

Klesc, M .

DISCRETE MATHEMATICS, 2002, 251 (1-3) :109-117

[7]

KLESC M, 1991, MATH SLOVACA, V41, P113

[8] CROSSING NUMBER OF C3 X CN [J].

RINGEISEN, RD ;

BEINEKE, LW .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 24 (02) :134-136

[9] Infinite families of crossing-critical graphs with given average degree [J].

Salazar, G .

DISCRETE MATHEMATICS, 2003, 271 (1-3) :343-350

[10]

WHITE AT, 1978, SELECTED TOPICS GRAP, P15

← 1 →