一个五阶图与星图的笛卡尔积交叉数

Crossing Numbers of Cartesian Products of Stars with 5-vertex Graph

确定图的交叉数被证明是一个NP-完全问题,因为其难度,能够确定交叉数的具体图类非常少.M.Klecˇ等人确定了一些关于阶数不超过5的图与路、星和圈的笛卡尔积图的交叉数.本文扩展了他们的结果,确定了1个5阶图与星图的笛卡尔积图的交叉数.

Garey and Johxon have proved that the problem to determine the crossing number of graphs is NP-complete, Because of its difficulty, presently the crossing number of some classes of special graphs is known. Marian Klesc has computed the crossing numbers of some the Cartesian products of 5-vertex graphs with paths, cycles and stars. In this paper these results are extended,and determine that the crossing number of Cartesian product of four specific 5-vertice graphs with star.