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

作者：袁梓瀚; 黄元秋

来源：运筹学学报, 2011, (03): 95-106.

DOI：10.15960/j.cnki.issn.1007-6093.2011.03.012

• 交叉数
• 泊松图P(4
• 1)
• 路
• 笛卡尔积 crossing number
• petersen graph P(4
• 1)
• paths
• Cartesian product

泊松图P(m,1)与路P_n的笛卡尔积的交叉数是一个NP-完全问题.Peng Y H和Yiew Y C证明了P(3,1)与P_n的笛卡尔积的交叉数为4n,而这篇文章证明了P(4,1)与P_n的笛卡尔积的交叉数为8n.

• 出版日期2011
• 单位湖南科技大学; 湖南师范大学