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

The Crossing Number of Petersen Graph P(4,1) with Paths P_n

作　　者：袁梓瀚[1] 黄元秋[2] 

机构地区：[1]湖南科技大学数学系,湖南湘潭411201 [2]湖南师范大学数学系,湖南长沙410081

出　　处：《运筹学学报》2011年第3期95-106,共12页Operations Research Transactions

基　　金：国家自然基金资助项目(10771062);教育部"新世纪优秀人才支持计划"(NCET-07-0276)

摘　　要：泊松图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.

关 键 词：交叉数 泊松图P(4 1) 路 笛卡尔积 

分 类 号：O157.5[理学—数学]