Hits:

Indexed by:期刊论文

Date of Publication:2008-05-28

Journal:Discrete Applied Mathematics

Included Journals:EI

Volume:156

Issue:10

Page Number:1892-1907

Abstract:Ringeisen and Beineke have proved that cr (C3 Cn) = n and cr (K4 Cn) = 3 n. Bokal has proved that cr (K1, l Pn) = (n - 1)  ?frac(l, 2)  ? ?frac(l - 1, 2)  ? In this paper we study the crossing numbers of Km Cnand Km, l Pn, and show (i) cr (Km Cn)  ?n · cr (Km + 2) for n  ?3 and m  ?5; (ii) cr (Km Cn)  ?frac(n, 4)  ?frac(m + 2, 2)  ? ?frac(m + 1, 2)  ? ?frac(m, 2)  ? ?frac(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 (Km, l Pn)  ?(n - 1) ( ?frac(m + 2, 2)  ? ?frac(m + 1, 2)  ? ?frac(l + 2, 2)  ? ?frac(l + 1, 2)  ?- ml) + 2 ( ?frac(m + 1, 2)  ? ?frac(m, 2)  ? ?frac(l + 1, 2)  ? ?frac(l, 2)  ?-  ?frac(m, 2)  ? ?frac(l, 2)  ? for min (m, l)  ?2, and equality holds for min (m, l) = 2. © 2007 Elsevier B.V. All rights reserved.