一个六阶图与星图的笛卡儿积的交叉数(英文)

The crossing number of cartesian product of star with a 6-vertex graph

图的交叉数已被证明是一个NP-完全问题,由于其难度,要知道图的确切交叉数是非常困难的.到目前为止,只知道少数图的交叉数,其中大部分是特殊图的笛卡儿积图的交叉数,比如路,圈以及星图与点数较"少"的图的笛卡儿积交叉数.在这些基础上,应用数学归纳法,把相关结果拓展到1个6-阶图G,并确定它与星的笛卡儿积交叉G×SnZ(6,n)+3[n/2].

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].