P6d=2与特殊图联图的交叉数

作者：王健; 叶永升^*; 张亚宾

来源：淮北师范大学学报(自然科学版), 2023, 44(02): 15-20.

• 交叉数
• 联图
• 直径
• 画法

图的交叉数是图的一个重要参数，由于确定一般图类的交叉数已被证明是一个NP-完全问题，并且目前能够确定交叉数的图类甚少，因此关于图的交叉数问题仍值得研究。基于Kleitman关于完全二部图交叉数cr(K6, n)=Z(6,n)的基础上，文章运用数学归纳与反证的方法，研究并确定六阶图P6d=2与n个孤立点、路Pn和圈Cn联图的交叉数分别为cr(P6d=2+Dn)=Z(6,n)+n,cr(P6d=2+Pn)=Z(6,n)+n+1和cr(P6d=2+Cn)=Z(6,n)+n+3。

• 单位
  淮北师范大学