数学研究
數學研究
수학연구
JOURNAL OF MATHEMATICAL STUDY
2011年
4期
411-417
,共7页
交叉数%笛卡尔积图%六阶图%星图
交扠數%笛卡爾積圖%六階圖%星圖
교차수%적잡이적도%륙계도%성도
Metacyclic p-groups%Extraspecial p-groups%Maximal subgroup
确定图的交叉数是NP．完全问题．目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z（6,n）＋2n＋[n/2].
確定圖的交扠數是NP．完全問題．目前已確定交扠數的六階圖與星圖的笛卡爾積圖極少。本文確定瞭—箇六階圖G與星圖5k積圖的交扠數為Z（6,n）＋2n＋[n/2].
학정도적교차수시NP．완전문제．목전이학정교차수적륙계도여성도적적잡이적도겁소。본문학정료—개륙계도G여성도5k적도적교차수위Z（6,n）＋2n＋[n/2].
Determining the crossing number of an arbitrary graph is NP-complete problem.Only a few crossing number of Cartesian products of the graph order 6 and stars had been determined. In this paper, we obtain the conclusion that cr（G × Sn） = Z（6,n）＋2n＋[n/2].
