Hits:

Indexed by:期刊论文

Date of Publication:2008-05-28

Journal:DISCRETE APPLIED MATHEMATICS

Included Journals:SCIE

Volume:156

Issue:10

Page Number:1892-1907

ISSN No.:0166-218X

Key Words:crossing number; Cartesian product; complete graph; complete bipartite graph

Abstract: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.