K_(1,1,2,2)×S_n的交叉数  

Crossing number of K_(1,1,2,2) × S_n

作　　者：苏振华[1] SU Zhenhua(Department of Mathematics,Huaihua University,Hunan 418008,China)

机构地区：[1]怀化学院数学系,湖南怀化418008

出　　处：《计算机工程与应用》2018年第14期52-55,共4页Computer Engineering and Applications

基　　金：湖南省教育厅科研项目(No.15C1090);湖南省自然科学基金(No.2017JJ3251)

摘　　要：确定图的交叉数是一个NP-完全问题。目前关于完全多部图与星图的积图交叉数的结果较少。根据完全多部图K_(1,1,2,2)的结构特点,引入收缩的方法,得到了积图K_(1,1,2,2) × S_n交叉数与完全多部图K_(1,1,2,2,n)交叉数的关系为cr(K_(1,1,2,2) × S_n)=cr(K_(1,1,2,2,n))+4n。Determining the crossing number of an arbitrary graph is NP-complete problem. There are known few results on the crossing numbers of Cartesian product for complete multipartite graphs with stars. This paper uses the structure characteristics of K_（1,1,2,2） and the contraction operations, obtains the relationship of crossing numbers of K_（1,1,2,2） × S_n with K_（1,1,2,2,n） is cr（K_（1,1,2,2） × S_n）= cr（K_（1,1,2,2,n））＋ 4n.

关 键 词：交叉数 笛卡尔积 星图 完全多部图 

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