The crossing number of cartesian product of star with a 6-vertex graph
Huang Yuan-qiu · Journal of Hunan University of Arts and Science · 2008
Computing the crossing number of a given graph has been proved to be NP-complete. It is very difficult to determine the exact crossing number of a given graph for its complicity. The crossing numbers of few families of graphs are known. So far, most of which are Cartesian Products of special graphs, such as Cartesian Products of paths, cycles or stars with small vertex graphs. On these basis, by using the induction method, this paper extends these results to a special 6-vertex graph G and then determines the crossing number of the Cartesian product of G × Sn is Z (6, n ) + 3 [ n/2] .