一个6阶图H与路P_n,圈C_n的联图的交叉数

周志东; 翟莹; 罗正炎

doi:10.16088/j.issn.1001-6600.2021012006

广西师范大学学报（自然科学版） ›› 2021, Vol. 39 ›› Issue (06) : 112 -118. DOI: 10.16088/j.issn.1001-6600.2021012006

一个6阶图H与路P_n,圈C_n的联图的交叉数

周志东, 翟莹, 罗正炎

作者信息 +

Author information +

文章历史 +

摘要

图的交叉数是表征图的一个重要参数,Garey和Johnson证明了确定图的交叉数是NP-完全问题。因为其难度,目前能够确定交叉数的图类甚少。在Kleitman给出的完全二部图的交叉数cr(K_6,n)=Z（6,n）的基础上,本文证明了一个6阶图H与n个孤立点nK₁、P_n及C_n的联图交叉数分别为cr（H+nK₁）=Z（6,n）+2■,cr（H+P_n）=Z（6,n）+2?■」和cr（H+Cn）=Z（6,n）+2?■」+2。