journal6 ›› 2005, Vol. 26 ›› Issue (2): 9-13.

• Mathematics • Previous Articles     Next Articles

The  Crossing  Numbers  of  Cartesian  Products of  Paths  with 6-Vertex  Graphs


  1. (Department of Mathematics,Normal University of Human,Changsha 410081,China)
  • Online:2005-04-15 Published:2012-09-22
  • About author:WANG Jing(1981-),female,was born in Shaoyang of Hunan Province,Master of Mathematics and Computer Science College,Hunan Normal University;research area is Graphy Theory and its application.
  • Supported by:

    Supported by National Natural Science Foundation of China(10271045)

Abstract: 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 “s
mall” 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.

Key words: graph, drawing, crossing number, path, cartesian products

WeChat e-book chaoxing Mobile QQ