The Crossing Numbers of Cartesian Products of Paths with 6-Vertex Graphs
Jing Wang, Huang Yuan-qiu · Journal of Jishou University · 2005
The crossing number of a graph is the minimum number of pairwise intersections of edges in a drawing of in the plane.It is well known that the crossing number of a graph is attained only in good drawings of the graph,which are those drawings where no edge crosses itself,no adjacent edges cross each other,and no two edges intersect more than once.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,this paper extends the results to the Cartesian Products of paths of length with four special 6-vertex graphs by using the induction method.