English

运筹学学报

• 运筹学 • 上一篇    下一篇

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

 袁梓瀚 黄元秋   

  1. 1. 湖南科技大学数学与计算科学学院
    2.
  • 收稿日期:2011-02-28 修回日期:2011-05-16 出版日期:2011-09-20 发布日期:2011-09-29
  • 通讯作者: 袁梓瀚 E-mail:yuanzihan2000@163.com

The crossing Number of Petersen graph P(4,1) with paths Pn

 YUAN  Zi-Han- Huang-Yuan-Qiu   

  • Received:2011-02-28 Revised:2011-05-16 Online:2011-09-20 Published:2011-09-29
  • Contact: YUAN zi-han E-mail:yuanzihan2000@163.com

PDF

1303

被引次数

1

摘要： 泊松图$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), 路, 笛卡尔积

Abstract: The crossing Number of Petersen graph $P(m,1)$ with paths $P_n$ is NP-complete problem, Y.H. Peng and Y.C.Yiew have determined the crossing Number of $P(3,1)$ with paths $P_n$ is $4n$, we have proved the crossing Number of $P(4,1)$ with paths $P_n$ is $8n$.

Key words:  crossing number, petersen graph P(4,1), paths, Cartesian product