Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418969 | Discrete Applied Mathematics | 2008 | 16 Pages |
Abstract
Ringeisen and Beineke have proved that cr(C3□Cn)=ncr(C3□Cn)=n and cr(K4□Cn)=3ncr(K4□Cn)=3n. Bokal has proved that cr(K1,l□Pn)=(n-1)⌊l2⌋⌊l-12⌋. In this paper we study the crossing numbers of Km□CnKm□Cn and Km,l□PnKm,l□Pn, and show (i) cr(Km□Cn)⩾n·cr(Km+2)cr(Km□Cn)⩾n·cr(Km+2) for n⩾3n⩾3 and m⩾5m⩾5; (ii) cr(Km□Cn)⩽n4⌊m+22⌋⌊m+12⌋⌊m2⌋⌊m-12⌋ for m=5,6,7m=5,6,7 and for m⩾8m⩾8 with even n⩾4n⩾4, and equality holds for m=5,6,7m=5,6,7 and for m=8,9,10m=8,9,10 with even n⩾4n⩾4 and (iii) cr(Km,l□Pn)⩽(n-1)(⌊m+22⌋⌊m+12⌋⌊l+22⌋⌊l+12⌋-ml)+2(⌊m+12⌋⌊m2⌋⌊l+12⌋⌊l2⌋-⌊m2⌋⌊l2⌋) for min(m,l)⩾2min(m,l)⩾2, and equality holds for min(m,l)=2min(m,l)=2.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zheng Wenping, Lin Xiaohui, Yang Yuansheng, Deng Chengrui,