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 permutations in determining crossing numbers J.Discussiones Mathematicae Graph Theory，2020，42（4）：1163-1183.9KlESCM，STA M，PETRILLOVA J.The crossing numbers of join of special disconnected graph on five vertices with discrete graphs J.Graphs and Combinatorics，2022，38（2）：1-19.10STA M.Determining crossing number of join of the discrete graph with two symmetric graphs of order five J.Symmetry，2019，11（2）：123.11STA M.On the crossing number of the join of the wheel on five vertices with the discrete graph J.Bulletin of the Australian Mathematical Society，2020，101（3）：353-361.12STA M.On the crossing numbers of join products of five graphs of order six with the discrete graph J.Opuscula Mathematica，2020，40（3）：383-397.13STA M.The crossing numbers of join products of paths and cycles with four graphs of order five J.Mathematics，2021，9（11）：1277.14OUYANG Z，HUANG Y，DONG F，et al.Zip product of graphs and crossing numbers J.Journal of Graph Theory，2021，96（2）：289-309.15DING Z，HUANG Y.The crossing numbers of join of some graphs with isolated vertices J.Discussiones MathematicaeGraph Theory，2018，38（4）：899-909.16KlESCM.The join of graphs and crossing numbers J.Electronic Notes in Discrete Mathematics，2007，28（1）：349-355.17TANG L，WANG J，HUANG Y.The crossing number of the join ofCmandPnJ.Mathematical Combinatorics，2007，1（1）：110-116.The Crossing Number of Join Product ofPd=26with Some Special GraphsWANG Jian，YE Yongsheng，ZHANG Yabin（School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China）Abstract：The crossing number of a graph is an important parameter of the graph.Since determining thecrossing number of a general graph class has been proved to be a NP-complete problem and there are fewgraph classes that can determine the crossing number，thus the issue of the crossing number of graphs is stillworth studying.Based on the conclusion of Kleitman that the crossing number of the complete bipartite graphcr(K6,n)=Z(6,n)，this article mostly uses mathematical induction and refutation to research and determine thecrossing number of join product of the sixth-order graphPd=26withnisolated vertices，the pathPnand thecycleCnarecr()Pd=26+Dn=Z(6,n)+n,cr()Pd=26+Pn=Z()6,n+n+1andcr()Pd=26+Cn=Z()6,n+n+3，respectively.Key words：crossing number；join product；diameter；drawing20