Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (14): 52-55.DOI: 10.3778/j.issn.1002-8331.1705-0081

Previous Articles     Next Articles

Crossing number of K1,1,2,2×Sn

SU Zhenhua   

  1. Department of Mathematics, Huaihua University, Huaihua, Hunan 418008, China
  • Online:2018-07-15 Published:2018-08-06



  1. 怀化学院 数学系,湖南 怀化 418008

Abstract: 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 [K1,1,2,2] and the contraction operations, obtains the relationship of crossing numbers of [K1,1,2,2×Sn] with [K1,1,2,2,n] is [cr(K1,1,2,2×Sn)=cr(K1,1,2,2,n)+4n].

Key words: crossing number, Cartesian product, star, complete multipartite graph

摘要: 确定图的交叉数是一个NP-完全问题。目前关于完全多部图与星图的积图交叉数的结果较少。根据完全多部图[K1,1,2,2]的结构特点,引入收缩的方法,得到了积图[K1,1,2,2×Sn]交叉数与完全多部图[K1,1,2,2,n]交叉数的关系为[cr(K1,1,2,2×Sn)=cr(K1,1,2,2,n)+4n]。

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