论文研究 [K1122×Sn]的交叉数.pdf

确定图的交叉数是一个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]。