P_%286%29%5E%28d%3D2%29与特殊图联图的交叉数.pdf

第44卷第2期2023年6月淮北师范大学学报（自然科学版）Journal of Huaibei Normal University(Natural Sciences)Vol.44 No.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。关键词：交叉数；联图；直径；画法中图分类号：O 157.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猜想当nm3时，CmCn的交叉数为(m-2)n，Zarankiewicz3对完全二部图Km,n的交叉数提出一个猜想（其中 x表示不超过x的最大整数）：cr(Km,n)=Z(m,n)=m2m-12n2n-12，Kleitman4证明该猜想对min(m,n)6成立。以Kleitman的结果为基础，Klesc 等5给出所有四阶图与Pn，Cn联图的交叉数，Beren等6-7与Klesc 等8-9给出一些五阶与六阶图与n阶离散图、路Pn和圈Cn联图的交叉数，更多结果可参见文献 10-15。基于Kleitman交叉数结果的基础上，本文研究并确定Pd=26与Dn联图的交叉数，并且确定Pd=26+Pn和Pd=26+Cn的交叉数。本文研究一个直径为2的六阶图Pd=26联图的交叉数，丰富交叉数的研究成果，为后人继续研究联图的交叉数提供研究的方法与途径。此外，多部图本质上是一个特殊图与n个孤立点的联图，从而确定联图的交叉数对于多部图的研究具有重要意义。1预备知识定义115G的一个好画法当且仅当对G的所有边有下列条件成立：（1）相同端点的两条边不交叉；收稿日期：2022-11-16基金项目：安徽省自然科学基金（KJ2016A633，KJ2021B04）作者简介：王健（1999），男，安徽合肥人，硕士生，研究方向为图论及其应用。通信作者：叶永升（1964），男，安徽嘉山人，硕士，教授，研究方向为图论及其应用。淮北师范大学学报（自然科学版）2023年（2）没有两条边交叉多于一点；（3）不超过两条边在同一点相交。定义215G+H表示G与H的联图，是将G的任一顶点与H的任一顶点相连所得的图。性质115设是G的一个好画法且A,B是G的边子集，cr(A,B)表示A与B的边交叉所得的交叉数，cr(A,A)记为cr(A)。对于G的3个边不相交子集A,B,C，有以下等式成立：cr()AB=cr()A+cr()B+cr()A,B,cr()AB,C=cr()A,C+cr()B,C。定义3Pd=kn是在Pn上添加最少的边获得的直径为k的图，即Pd=kn中任意2个顶点u，v，其距离都小于等于k。本文所研究的图Pd=2n的2种不同画法见图1。2Pd=26+Dn的交叉数Pd=26+Dn表示Pd=26与n个孤立顶点t1,t2,tn的联图，其中ti对Pd=26的顶点都是相邻的，i=1,2,3,n，见图2。图35为Pd=26在同构意义下的不同画法。Ti表示与顶点ti相关联的六条边所生成的子图，Fi=Pd=26Ti,i=1,2,3,n，有以下等式成立：Pd=26+Dn=Pd=26K6,n=Pd=26i=1nTi。（1）图1Pd=26的2种画法图2Pd=26+Dn的一个好画法图3cr(Pd=26)=0图4cr(Pd=26)=1性质2cr(Pd=26+D2)=2。证 明由 图 6 知cr(Pd=26+D2)2，由 于Pd=26+D2包 含K3,3作 为 子 图 且cr(K3,3)=1，因 此cr(Pd=26+D2)1。假设存在Pd=26+D2的一种好画法使得cr(Pd=26+D2)=1，由定义可知交叉数是由2条边交叉产生，当删除一条图6中非曲线边的交叉边时，与Pd=26+D2删去一条边后仍然包含K3,3作为子图相矛盾。因此cr(Pd=26+D2)=2。定理1cr()Pd=26+Dn=6n2n-12+n,n1。证明由图2可知cr(Pd=26+Dn)6n2n-12+n，下面通过对n使用数学归纳法来证明cr(Pd=26+Dn)6n2n-12+n,n=1的情形是平凡的，由性质2可知n=2是成立的。现在假设当3mn时，有cr()Pd=26+Dm6m2m-12+m。（2）下面证明m=n的情形成立，考虑Pd=26+Dn的一个好画法使得cr()Pd=26+Dn6n2n-12+n。因此在这个画法下Pd=26的边彼此交叉。假设Tn与Pd=26不发生交叉，由于Pn的边不发生交叉，那么假设所有的ti都放在Fn的外部，其中i=1,2,n-1。易证Fn与Ti至少相交4次，且当cr(Fn,Ti)=4时，有cr(Pd=26,Ti)2。由于cr(Pd=26)0且Pd=26与其他边最多相交n次，因此至少存在1个子图Ti与Fn相交5次，所以有cr(Pd=26+Pn)=cr(K6,n-1)+cr(Fn)+cr(Fn,K6,n-1)6n-12n-22+1+4(n-2)+56n2n-12+n,与假设相矛盾，从而完成证明。引理 116设是图Dm+Cn的一个好画法，m2,n2。若Cn自身的边不交叉且r个子图Ti1,Ti2,Tir不与Cn发生交叉，2rm，那么任意2个子图Tij和Tik在下相互交叉至少n2n-12次，对任意的j,k=1,2,r,jk都成立。图8Pd=26+Pn的一个好画法18第2期王健等：Pd=26与特殊图联图的交叉数引理217对任意图G，设是G+Cn的一个最优画法，则Cn自身不交叉。定理3cr()Pd=26+Cn=6n2n-12+n+3,n3。证明 由图 9 可知，cr(Pd=26+Cn)6n2n-12+n+3,且Pd=26+Pn是Pd=26+Cn的子图，有cr(Pd=26+Cn)cr(Pd=26+Pn)6n2n-12+n+1,所以6n2n-12+n+1cr(Pd=26+Cn)6n2n-12+n+3。现在证明下列断言成立，则定理成立。断言1不存在画法使得cr(Pd=26+Cn)=6n2n-12+n+1。假设存在这样一个好画法1使得cr1(Pd=26+Cn)=6n2n-12+n+1。情形1在画法1下Cn的边不存在交叉，因此Pd=26的顶点要么放在Cn的内部，要么放在外部，如不特殊说明默认Pd=26的顶点放在Cn的内部。用TVi表示Pd=26的顶点vi与Cn的n个顶点t1,t2,tn相连所生成的边集，且Cn与TVi不相交，i=1，2，6，则由引理1cr1()Pd=26+Cn62n2n-126n2n-12+n+1。情形2在画法1下Cn存在交叉，假设Cn的边存在一个交叉，删去这条边将会导致Pd=26+Pn的交叉数小于6n2n-12+n+1，矛盾。断言2不存在画法使得cr(Pd=26+Cn)=6n2n-12+n+2。假设存在一个好画法2使得cr2(Pd=26+Cn)=6n2n-12+n+2。情形1在画法2下Cn与其他边不交叉，则Pd=26的顶点全在Cn的内部，且Cn与Tvi都不相交，则由引理1cr2()Pd=26+Cn62n2n-126n2n-12+n+2。情形2在画法2下Cn存在交叉且最多相交2次，由引理2可知cr2(E(Cn)=0。（1）若Cn与Pd=26相交2次且Cn与所有Tvi不相交，则Pd=26的4个顶点v1,v2,v3,v4在Cn的内部，否则将在Cn上产生至少3个交叉。对于剩下的2个顶点，有以下可能：当Pd=26的6个顶点都在Cn的内部时，由于Cn与Tvi都不相交，由引理1cr2()Pd=26+Cn62n2n-126n2n-12+n+2。当Pd=26的1个2-度顶点在Cn的外部时，其余5个顶点在Cn的内部，则由引理1cr2()Pd=26+Cn52n2n-126n2n-12+n+2。当Pd=26的2个2-度顶点在Cn的外部时，其产生4个交叉，显然矛盾。（2）Cn与Tvi相交且至多产生2个交叉，则Cn与Pd=26不相交，否则将在Cn的边上产生至少4个交叉，矛盾。因此Pd=26的顶点全在Cn的内部，则由引理1可得cr2()Pd=26+Cn62n2n-126n2n-12+n+2。4结语在Kleitman对完全二部图交叉数的研究结果上，文章对六阶图Pd=26与n阶离散图Dn、路Pn和圈Cn联图的交叉数进行了确定。在证明过程中，由于图画法涉及到n+6个点与6n条边，主要采用数学归纳图9Pd=26+Cn的一个好画法19淮北师范大学学报（自然科学版）2023年与反证的思想来证明Pd=26联图的交叉数。在本文研究的基础上可以继续研究Pd=36和Pd=46与n阶离散图、路Pn和圈Cn联图的交叉数。参考文献：1WEST D B.Introduction to graph theory M.Second Edition.Upper Saddle River：Prentice hall，2001：1-588.2HARARY F，KAINEN P C，SCHWEKN A.Toroidal graphs with arbitrarily high crossing numbers J.Nanta Mathematica，1973，6（1）：58-67.3ZARANKIEWICZ K.On a problem of P.Turan concerning graphs J.Fundamenta Mathematicae，1955，1（41）：137-145.4KLEITMAN D J.The crossing number ofK5,nJ.Journal of Combinatorial Theory，1970，9（4）：315-323.5KlESCM，SCHRTTER S.The crossing numbers of join products of paths with graphs of order fourJ.DiscussionesMathematicae Graph Theory，2011，31（2）：321-331.6BERENY S，STA M.Cyclic permutations and crossing numbers of join products of symmetric graph of order six J.Carpathian Journal of Mathematics，2018，34（2）：143-155.7BERENY S，STA M.Cyclic permutations and crossing numbers of join products of two symmetric graphs of order sixJ.Carpathian Journal of Mathematics，2019，35（2）：137-146.8KlESCM，STA M.Cyclic permutatio