点击次数：

论文类型：期刊论文

发表时间：2011-01-01

发表刊物：ARS COMBINATORIA

收录刊物：Scopus、SCIE

卷号：98

页面范围：433-445

ISSN号：0381-7032

关键字：crossing number; Cartesian product; cone graph; path; wheel

摘要：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.