C8+{e1}，C8+{e1}+{e2}与Pn的笛卡儿积的交叉数

C8+{e1}，C8+{e1}+{e2}与Pn的笛卡儿积的交叉数
 
摘要：已经证明确定图的交叉数是1个NP完全问题(见文献[1])。本文研究了两个特殊的笛卡儿积图的交叉数 。确定了笛卡儿积图（C8+{e1}） Pn（n 1）的交叉数, 以及笛卡儿积图（C8+{e1}+{e2}） Pn（n 1）的交叉数，其中e1，e2 vivi+2(i=1,2,…,8,i+2(mod 8)),若e1的端点为vj, vj+2,那么e2的端点不为vj+1。
关键字：图；画法；交叉数；C8；笛卡儿积；同胚； Pn

The crossing number of C8+{e1} and C8+{e1}+{e2} with Pn
 
Abstrct: Determing the crossing numbers of graphs has been proved to be NP-complete. In this paper,we study the crossing numbers of two special Cartesian product graphs .We have proved the crossing number of (C8+{e1}) Pn and (C8+{e1}+{e2}) Pn(n 1), e1,e2 vivi+2(i=1,2,…,8,i+2(mod 8)), If the endpoints of e1 are vj,vj+2(j =1,2,…,8,i+2(mod 8)), then the endpoints of e2 aren,t vj+1.
Keywords: graph;  drawing;  crossing number;   C8;   the cartesian product;  homeomorphism;  Pn