一个六阶图与路的笛卡尔积交叉数

On the Crossing Numbers of Cartesian Product of a 6-vertices Graph with Paths

确定图的交叉数是一个完全NP-问题,因为其难度,所以我们能够确定交叉数的图类很少.本文先构造F×Pn≤2n的一种好画法,由这种好画法计算出Cr(F×Pn)≤4n,然后利用数学归纳法证明Cr(F×Pn)≥4n,从而确定了F与Pn的笛卡尔积交叉数即Cr(F×Pn)=4n.

Determining the crossing numbers of graphs is NP-complete. Because of the complexity of the problem , there are a few exact results on the crossing numbers of graphs. In this paper, we first consider a good drawing of F x Pn and through this find Cr（F × Pn） ≤ 4n good drawing ; then we proved that Cr（F × Pn） ≥ 4n by induction, so we assert that Cr（F × Pn） ≥4n.