泊松图P(4,1)与路Pn的笛卡尔积的交叉数

摘要

泊松图P(m,1)与路Pn的笛卡尔积的交叉数是一个NP-完全问题.Peng Y H 和Yiew Y C证明了P(3,1)与R的笛卡尔积的交叉数为4n,而这篇文章证明了P(4,1)与Pn的笛卡尔积的交叉数为8n.%The crossing number of Petersen graph P(m,1) with paths Pn is NP-complete problem. Peng Y H and Yiew Y C have determined the crossing number of P(3,1) with paths Pn is An, and we have proved the crossing number of P(4,1) with paths Pn is 8n.