| 泊松图P(4,1)与路Pn的笛卡尔积的交叉数 |
| |
| 引用本文： | 袁梓瀚,黄元秋.泊松图P(4,1)与路Pn的笛卡尔积的交叉数[J].运筹学学报,2011,15(3):95-106. |
| |
| 作者姓名： | 袁梓瀚 黄元秋 |
| |
| 作者单位： | 1. 湖南科技大学数学与计算科学学院
2. |
| |
| 基金项目： | 国家自然基金资助项目(10771062); 教育部“新世纪优秀人才支持计划”(NCET-07-0276) |
| |
| 摘 要： | 泊松图$P(m, 1)$与路$P_n$的笛卡尔积的交叉数是一个NP-完全问题, Y.H. Peng和Y.C.Yiew 证明了$P(3,1)$与$P_n$的笛卡尔积的交叉数为$4n$, 我们证明明了$P(4,1)$与$P_n$的笛卡尔积的交叉数为$8n$.
|
| 关 键 词： | 交叉数 泊松图P(4 1) 路 笛卡尔积 |
| 收稿时间： | 2011-02-28 |
| 修稿时间： | 2011-05-16 |
The Crossing Number of Petersen Graph P(4, 1) with Paths Pn |
| |
| YUAN Zihan,HUANG Yuanqiu.The Crossing Number of Petersen Graph P(4, 1) with Paths Pn[J].OR Transactions,2011,15(3):95-106. |
| |
| Authors: | YUAN Zihan HUANG Yuanqiu |
| |
| Institution: | YUAN Zihan HUANG Yuanqiu 1.Department of Mathematics,Hunan University of Science and Technology,Xiangtan 411201,China 2.Department of Mathematics,Normal University of Hunan,Changsha 410081,China |
| |
| Abstract: | The crossing number of Petersen graph P(m,1) with paths P_n is NP-complete problem.Peng Y H and Yiew Y C have determined the crossing number of P(3,1) with paths P_n is 4n,and we have proved the crossing number of P(4,1) with paths P_n is 8n. |
| |
| Keywords: | crossing number petersen graph P(4 1) paths Cartesian product |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
