第44卷第2期2023年6月淮北师范大学学报（自然科学版）JournalofHuaibeiNormalUniversity(NaturalSciences)Vol.44No.2Jun.2023Pd=26与特殊图联图的交叉数王健，叶永升，张亚宾①（淮北师范大学数学科学学院，安徽淮北235000）摘要：图的交叉数是图的一个重要参数，由于确定一般图类的交叉数已被证明是一个NP-完全问题，并且目前能够确定交叉数的图类甚少，因此关于图的交叉数问题仍值得研究。基于Kleitman关于完全二部图交叉数cr(K6,n)=Z(6,n)的基础上，文章运用数学归纳与反证的方法，研究并确定六阶图Pd=26与n个孤立点、路Pn和圈Cn联图的交叉数分别为cr()Pd=26+Dn=Z(6,n)+n,cr()Pd=26+Pn=Z()6,n+n+1和cr()Pd=26+Cn=Z()6,n+n+3。关键词：交叉数；联图；直径；画法中图分类号：O157.5文献标识码：A文章编号：2095-0691（2023）02-0015-060引言图G=(V(G),E(G))，其中V(G),E(G)分别是G的顶点集与边集，本文的图都为简单无向连通图。G的交叉数cr(G)定义为G的所有好画法中边交叉的最小数目。Dn,Pn和Cn分别表示n个孤立顶点，n个顶点的路和圈。d(u,v)表示u,v之间的距离，即从u到v最短路的长度，若2个顶点之间没有路，其距离定义为无穷大。离心率εG(v)表示从v到离v最远顶点的距离，直径diam(G)是G顶点离心率中最大的。本文所有符号、概念参看文献［1］。图的交叉数是图的拓扑性质，研究图的交叉数不但具有较强的理论依据，且在实际生活中有广泛的应用，如在城市道路规划，电子线路设计以及CAD等领域都有着广泛应用。Harary等［2］猜想当n⩾m⩾3时，Cm□Cn的交叉数为(m-2)n，Zarankiewicz［3］对完全二部图Km,n的交叉数提出一个猜想（其中ëûx表示不超过x的最大整数）：cr(Km,n)=Z(m,n)=êëúûm2êëúûm-12êëúûn2êëúûn-12，Kleitman［4］证明该猜想对min(m,n)⩽6成立。以Kleitman的结果为基础，Klešč等［5］给出所有四阶图与Pn，Cn联图的交叉数，Berežn等［6-7］与Klešč等［8-9］给出一些五阶与六阶图与n阶离散图、路Pn和圈Cn联图的交叉数，更多结果可参见文献［10-15］。基于Kleitman交叉数结果的基础上，本文研究并确定Pd=26与Dn联图的交叉数，并且确定Pd=26+Pn和Pd=26+Cn的交叉数。本文研究一个直径为2的六阶图Pd=26联图的交叉数，丰富交叉数的研究成果，为后人继续研究联图的交叉数提供研究的方法与途径。此外，多部图本质上是一个特殊图与n个孤立点的联图，从而确定联图的交叉数对于多部图的研究具有重要意义。1预备知识定义1...
