Hits:

Indexed by:期刊论文

Date of Publication:2011-01-01

Journal:ARS COMBINATORIA

Included Journals:Scopus、SCIE

Volume:98

Page Number:433-445

ISSN No.:0381-7032

Key Words:crossing number; Cartesian product; cone graph; path; wheel

Abstract:Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(W-l,W-m square P-n), the crossing number of Cartesian product W-l,W-m square P-n, where W-l,W-m be the cone graph C-m + (K-l) over bar. Klesc showed that cr(W-1,W-3 square P-n) = 2n(Journal of Graph Theory, 6(1994), 605-614), cr(W-1,W-4 square P-n) = 3n - 1 and cr(W-2,W-3 square P-n) = 4n(Discrete Mathematics, 233(2001), 353-359). Huang et al. showed that cr(W-1,W-m square P-n) = (n - 1)[m/2][m-1/ 2] + n + 1 for n <= 3(Journal of Natural Science of Hunan Normal University, 28(2005), 14-16). We extend these results and prove cr(W-1,W-m square P-n) = (n -1)[m/2][m-1/ 2] + n + 1 and cr(W-2,W-m square P-n) = 2n[m/2][m-1/ 2] + 2n.