摘要
泊松图P(m,1)与路P_n的笛卡尔积的交叉数是一个NP-完全问题.Peng Y H和Yiew Y C证明了P(3,1)与P_n的笛卡尔积的交叉数为4n,而这篇文章证明了P(4,1)与P_n的笛卡尔积的交叉数为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 4n, and we have proved the crossing number of P（4, 1） with paths Pn is 8n.
出处
《运筹学学报》
CSCD
2011年第3期95-106,共12页
Operations Research Transactions
基金
国家自然基金资助项目(10771062)
教育部"新世纪优秀人才支持计划"(NCET-07-0276)
关键词
交叉数
泊松图P(4
1)
路
笛卡尔积
crossing number, petersen graph P（4, 1）, paths, Cartesian product
