一类特殊五阶图与n个孤立顶点的联图的交叉数
来源期刊：昆明理工大学学报(自然科学版)2020年第1期
论文作者：何翠芳 吕胜祥
文章页码：119 - 256
关键词：联图;交叉数;二部图;画法;
摘 要：图的交叉数是图的一个重要参数,1983年Garey和Johnson证明了确定图的交叉数问题是一个NP-完全问题.令H为一个简单五阶图,Hn是图H与n个孤立顶点的联图.当n=1,2,3,4,5且p=1或2时,若都有Cr（Hn）≥Z（5,n）+p[n/2]+Cr（E（H））,则当n> 5时,也成立Cr（Hn）≥Z（5,n）+p[n/2]+Cr（E（H））.
何翠芳1，吕胜祥1,2
1. 湖南科技大学数学与计算科学学院2. 湖南财政经济学院数学与统计学院
摘 要：图的交叉数是图的一个重要参数,1983年Garey和Johnson证明了确定图的交叉数问题是一个NP-完全问题.令H为一个简单五阶图,Hn是图H与n个孤立顶点的联图.当n=1,2,3,4,5且p=1或2时,若都有Cr（Hn）≥Z（5,n）+p[n/2]+Cr（E（H））,则当n> 5时,也成立Cr（Hn）≥Z（5,n）+p[n/2]+Cr（E（H））.
关键词：联图;交叉数;二部图;画法;
