K_(2,4)×S_n的交叉数

ON THE CROSSING NUMBER OF K_(2,4) × S_n

摘要Garey和Johnson证明了确定图的交叉数是一个NP-完全问题.确定了笛卡尔积图K_(2,4)×S_n的交叉数是Z(6,n)+4n.当m≥5,猜想cr(K_(2,m)×S_n)=cr(K_(2,m,n))+n[m/2][m-1/2].

Garey and Johnson proved that the problem of determining the crossing number of an arbitrary graph is NP-complete.In this paper,it is proved that the crossing number of the Cartesian product K2,4）×Sn is Z（6,n） ＋ 4n.For m≥5,we conjecture that CT（K2,m）×Sn） = cr（K2,m,n） ＋n[m/^2][m-1/2].