6-阶图与路的笛卡儿积交叉数(英文)

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

图的交叉数是指把图画在平面上边与边产生的交叉数目的最小值。图的交叉数只在好画法中得到,好画法是指满足边自身不交叉,相关联的边不交叉,任意两条交叉的边至多交叉一次的画法。图的交叉数已被证明是一个NP-完全问题,由于其难度,要知道图的确切交叉数是非常困难的。到目前为止,只知道少数图的交叉数,其中大部分是特殊图的笛卡儿积图的交叉数,比如路,圈以及星图与点数较“少”的图的笛卡儿积交叉数。在这些基础上,应用数学归纳法,把相关结果拓展到4个6-阶图与长为的路的笛卡儿积交叉数。

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.