点击次数：

论文类型：期刊论文

发表时间：2008-05-28

发表刊物：DISCRETE APPLIED MATHEMATICS

收录刊物：SCIE

卷号：156

期号：10

页面范围：1892-1907

ISSN号：0166-218X

关键字：crossing number; Cartesian product; complete graph; complete bipartite graph

摘要：Ringeisen and Beineke have proved that cr(C-3 square C-n) = n and cr (K-4 square C-n) = 3n. Bokal has proved that cr(K-1,K-l square P-n) = (n - 1) [l/2] [l-1/2]. In this paper we study the crossing numbers of K-m square C-n and K-m,K-l square P-n, and show (i) cr(K-m square C-n) >= n.cr(Km+2) for n >= 3 and m >= 5; (ii) cr(K-m square C-n)<= n/4[m+2/2][m+1/2][m/2][m-1/2] for m = 5,6,7 and for m >= 8 with even n >= 4, and equality holds for m = 5,6,7 and for m = 8,9,10 with even n >= 4 and (iii) cr(K-m,K-l square P-n)<=(n - 1) ([m2/2][m+1/2][l+2/2][l+1/2] - ml) + 2([m+1/2][m/2][l+1/2][l/2] - [m/2][l/2]) for min (m, l)>= 2, and equality holds for min(m,l) = 2. (C) 2007 Elsevier B.V. All rights reserved.