The Crossing Numbers of Cartesian Product of Cone Graph C-m + (K-l)over-bar with Path P-n
Release Time:2019-03-09 Hits:
Indexed by: Journal Article
Date of Publication: 2011-01-01
Journal: ARS COMBINATORIA
Included Journals: SCIE、Scopus
Volume: 98
Page Number: 433-445
ISSN: 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.