六阶图G与Sn的积图的交叉数

摘要

Determining the crossing number of an arbitrary graph is NP-complete problem.Only a few crossing number of Cartesian products of the graph order 6 and stars had been determined. In this paper, we obtain the conclusion that cr（G × Sn） = Z（6,n）＋2n＋[n/2].%确定图的交叉数是NP．完全问题．目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z（6,n）＋2n＋[n/2].