岳为君 黄元秋

摘要 联图G∨H表示将G中每个点与H中的每个点连边得到的图.在Klecˇ给出所有3阶图和4阶图与圈Cn的联图的交叉数的基础上，确定了一个5阶图与圈Cn的联图的交叉数.

关键词画法；交叉数；联图；圈

中图分类号O1575文献标识码A文章编号10002537（2015）01008105

The Crossing Number of Join Products of a Special 5Vertex Graph with Cn

文中未说明的概念和术语均同文献[1]，且无特别说明所涉及的图G=（V（G），E（G））均指简单连通图.图G在平面上的一个好画法是指满足以下4个条件的画法：

（1）任意两条边最多交叉一次；

（2）边不能自身交叉；

（3）任意相邻的两条边不能交叉；

（4）没有三条边交叉于同一个点.

crD（G）表示在好画法D下G中边与边之间的交叉数目.而图G的交叉数，记为cr（G），是指这样一个值：cr（G）=minD{crD（G）}，其中D取遍G的所有好画法.若D是G的一个好画法，使得crD（G）=cr（G），则称D是G的一个最优画法.

图的交叉数是图的一个重要参数，自从图的交叉数概念提出以来，国内外许多学者都做出了很多的研究.但由于确定图的交叉数是NP问题[2]，至今在确定图类的交叉数研究中，主要是针对一些具有特殊结构的图类，如完全2部图Km，n[3]，完全多部图[46]，或者一些图与图作某种运算后得到的图，如路或圈与一些低阶图的笛卡尔积图[79].特别地，关于完全2部图Km，n，Kleitman在文献[3]中证明了当min{m，n}≤6时，Zarankiewicz猜想[10]成立，即Km，n的交叉数为：cr（Km，n）=Z（m，n）=m2」m-12」n2」n-12」（min{m，n}≤6），这里，对任意实数x，x」表示不超过x的最大整数.

设G和H是两个无公共顶点的简单图，联图G∨H表示这样的一个图：顶点集V（G∨H）=V（G）∪V（H），边集E（G∨H）=E（G）∪E（H）∪{e（u，v）|u∈V（G），且v∈V（H）}，其中e（u，v）表示连接顶点u和v的边.设是图G的一个好画法，对G的任意边子集A和B，记号cr（A）表示在画法下，A中的边之间产生的交叉数；记号cr（A，B）表示在画法下，A中边与B中的边之间产生的交叉数.显然，当A=E（G）时，cr（A）=cr（G）.

图1H的一个好画法

Fig.1A good illustration of H

目前，有关联图的交叉数方面的研究结果较少.Oporowski在文献[11]中确定了C3∨C6的交叉数.文献[12]确定了Pm∨Pn，Pm∨Cn和Cm∨Cn的交叉数.Klecˇ在文献[13]中，得到了所有3阶、4阶图G与路Pn与圈Cn的联图的交叉数.文献[14]确定了当m=，3，4，5时Sm∨Pn的交叉数，以及m=3，4时Sm∨Cn的交叉数.本文中Pn和Cn分别表示长为n的路，长为n的圈.Sn表示星图K1，n.

设H是如图1所示的一个5阶图，是文献[14]中的S4加3条边得到的，E（H）=E（S4）∪{t1t2，t2t3，t3t4}.

本文确定了H与圈Cn的联图的交叉数，主要结果如下：

定理设H是如图1所示的一个5阶图，Cn（n≥3）表示长为n的圈，则有

cr（H∨Cn）=Z（5，n）+2n2」+3.

1基本性质和引理

在证明本文的主要结果之前，先给出一些基本性质和引理.

首先，由交叉数的定义，易有如下性质：

性质11令D是图G的一个好画法，且A，B，C是图G的3个边不相交的子图，则有

（1）crD（A∪B）=crD（A）+crD（B）+crD（A，B）.

（2）crD（A∪B，C）=crD（A，C）+crD（B，C）.

性质12若图H是G的子图，则有cr（H）≤cr（G）.

性质13若图G与图H同构，则有cr（G）=cr（H）.

引理11[3]cr（K4，n）=Z（4，n），cr（K5，n）=Z（5，n）.

引理12[5]cr（K1，4，n）=Z（5，n）+2n2」，n≥3.

引理13[12]设G为任意图，且是Cn∨G的一个最优画法，则圈Cn自身不会相交，即cr（Cn）=0.

引理14[14]cr（S3∨Cn）=Z（4，n）+n2」+2，cr（S4∨Cn）=Z（5，n）+2n2」+2，n≥3.

引理15[13]cr（W3∨Cn）=Z（4，n）+n+4，n≥3，cr（W3∨Pn）=Z（4，n）+n+1，n≥2.

引理16[15]cr（W4∨Pn）=Z（5，n）+n+n2」+1，n≥2，cr（W5∨Pn）=Z（6，n）+n+3n2」+1，n≥2.

引理17设Cn=v1v2…vnv1为一个长为n的圈，Cn在平面上围成一个圆盘D，在D的内部放置m个点xj（1≤j≤m），xj与每个vi（1≤i≤n）连边，记这样的边组成的集合为Txj.若是使得所有边集Txj都画在圆盘D的内部的一个好画法，即cr（∪mj=1Txj，Cn）=0，则∪mj=1Txj在画法产生的交叉数，满足cr（∪mj=1Txj）≥C2mn2」n-12」.

证在圆盘内任取两个点xi，xj（1≤i，j≤m，i≠j），我们来估计cr（Txi，Txj）的值.在圆盘D的外部置一点xk（k≠i，k≠j），且xk与每个vi连边（1≤i≤n），且使得每条边xkvi，1≤i≤n画在圆盘D的外部，即这些边与其他任何边不会交叉.这样得到完全2部图K3，n的一个画法′，使得cr′（K3，n）=cr（Txi，Txj）.由文献[3]可知cr（K3，n）=Z（3，n），所以cr（Txi，Txj）=cr′（K3，n）≥cr（K3，n）=n2」n-12」.由点xi，xj的任意性，在画法下cr（∪mj=1Txj）≥C2mn2」n-12」.

2定理的证明

先规定有关记号：H表示特殊的一个5阶图，如图1；V（H）={t0，t1，t2，t3，t4}，其中t0表示H的中心点，而ti（1≤i≤4）表示图H的另外4个点；V（Cn）={v1，v2，…，vn}，En=E（Cn）；对每个0≤i≤4，记Ti={tivj|1≤j≤n}；E0={t0ti|1≤i≤4}.又对于H∨Cn的任意边子集A，用〈A〉表示由A导出的子图.

当n=3时，H∨C3同构于W3∨P4，根据性质23和引理25，

cr（H∨C3）=cr（W3∨P4）=Z（4，4）+4+1=Z（5，3）+232」+3，结论成立.

当n=4时，H∨C4同构于W4∨P4，根据性质23和引理26，

cr（H∨C4）=cr（W4∨P4）=Z（5，4）+4+2+1=Z（5，4）+242」+3，结论成立.

当n=5时，H∨C5同构于W5∨P4，根据性质23和引理26，

cr（H∨C5）=cr（W5∨P4）=Z（6，4）+4+6+1=Z（5，5）+252」+3，结论成立.

接下来考虑n≥6的情况.

先在平面上构造靠边H∨Cn的一个好画法，使得cr（H∨Cn）=Z（5，n）+2n2」+3.

画法在平面直角坐标系x-y上的构造如下：

（1）从原点出发把v1，v2，…，vn2」从左至右依次放置在x的正半轴上；

（2）从原点出发把vn，vn-1，…，vn2」从右至左依次放置在x轴的负半轴上；

（3）点t2，t1依次放置在y轴的正半轴上，点t4，t3依次放置在y轴的负半轴上，t0放置在点（ε，ε）位置上，这里ε是很小的正数；

图2H∨Cn的一个好画法

Fig.2A good illustration of H∨Cn

（4）除了边vn2」vn2」和t2t3外，H∨Cn的其余所有边用直线段连接，而边vn2」vn2」和t2t3用弧线连接，使得边t2t3仅与边vn2」vn2」交叉，如图2是由此构造的一个好画法.

在画法下计算cr（H∨Cn）的值.去掉En，E0的边和边t1t2，t2t3，t3t4后，得到完全2部图K5，n的一个最优画法[3].根据引理21，cr（K5，n）=Z（5，n）.另外，不难得到，cr（En，E0）=2，cr（En，t2t3）=1，cr（E0，∪4i=0Ti）=2n2」.因此cr（H∨Cn）=Z（5，n）+2n2」+3，所以cr（H∨Cn）≤Z（5，n）+2n2」+3.

下面用反证法证明cr（H∨Cn）≥Z（5，n）+2n2」+3.若不然，假设存在H∨Cn的一个好画法θ，不妨设θ是最优画法，使得crθ（H∨Cn）≤Z（5，n）+2n2」+3，即有

crθ（H∨Cn）≤Z（5，n）+2n2」+2，（*）

以下证明总能得到一个与（*）式相矛盾的结论，从而完成定理的证明.

为了方便，用P3表示H中路t1t2t3t4的边组成的集合，即P3={t1t2，t2t3，t3t4}，又En=E（Cn），则H∨Cn的边可分解为如下边不相交的集的并，即E（H∨Cn）=E0∪P3∪∪4i=0

Ti∪En.则有以下断言：

断言21crθ（P3，En）+crθ（P3，E0）+crθ（P3，∪4i=0Ti）+crθ（P3）=0，即在θ下，路P3的边无交叉.

因为〈E0∪（∪4i=0Ti）∪En〉同构于S4∨Cn，根据性质21和引理24可得：

crθ（H∨Cn）=crθ（E0∪P3∪（∪4i=0Ti）∪En）=

crθ（E0∪∪4i=0Ti∪En）+crθ（E0∪（∪4i=0Ti）∪En，P3）+crθ（P3）≥

cr（S4∨Cn）+crθ（E0∪（∪4i=0Ti）∪En，P3）+crθ（P3）=

Z（5，n）+2n2」+2+crθ（E0∪（∪4i=0Ti）∪En，P3）+crθ（P3）.

由于（*）式crθ（H∨Cn）≤Z（5，n）+2n2」+2.所以，crθ（E0∪（∪4i=0Ti）∪En，P3）+crθ（P3）=0.则有crθ（P3，En）+crθ（P3，E0）+crθ（P3，∪4i=0Ti）+crθ（P3）=0.

断言22crθ（E0，En）+crθ（∪4i=0Ti，En）≤2，即在θ下圈Cn的边上至多有两个交叉.

因为〈E0∪（∪4i=0Ti）〉包含子图K1，4，n根据性质21和引理22可得：

crθ（H∨Cn）=crθ（E0∪P3∪（∪4i=0Ti）∪En）=

crθ（E0∪（∪4i=0Ti））+crθ（E0∪（∪4i=0Ti），P3∪En）+crθ（P3∪En）≥

Z（5，n）+2n2」+crθ（E0∪（∪4i=0Ti），P3∪En）+crθ（P3∪En）.

由于（*）式crθ（H∨Cn）≤Z（5，n）+2n2」+2.所以，crθ（E0∪（∪4i=0Ti），P3∪En）+crθ（P3∪En）≤2.根据性质21和断言21，crθ（E0∪（∪4i=0Ti），P3∪En）=crθ（E0∪（∪4i=0Ti），P3）+crθ（E0∪（∪4i=0Ti），En）≥crθ（E0，En）+crθ（∪4i=0Ti，En）则有crθ（E0，En）+crθ（∪4i=0Ti，En）≤2.

断言23crθ（E0，En）=0或2，即圈与星不交叉或恰交叉两次.

由断言21知crθ（P3，En）=0，则P3的4个顶点{t1，t2，t3，t4}都在Cn的同一区域，又由断言22 crθ（E0，En）≤2，如果t0与t1，t2，t3，t4不在同一区域，则crθ（E0，En）≥4，所以H的5个顶点都在同一区域，且crθ（E0，En）=0或者crθ（E0，En）=2.由引理23知Cn把平面分成2个区域，不妨设H的5个顶点都在Cn围成区域的内部.

在下面的讨论中，我们在不计算crθ（E0，En）的情况下，就能得到H∨Cn最优画法θ下的交叉数与（*）式矛盾.即crθ（E0，En）=0或crθ（E0，En）=2不影响我们的计算结果，不妨设crθ（E0，En）=0.

根据断言22可知crθ（∪4i=0Ti，En）≤2，下面分3种情形进行讨论：

情形21crθ（∪4i=0Ti，En）=0，H中5个顶点都满足引理27的条件，根据引理27

crθ（H∨Cn）≥crθ（∪4i=0Ti）≥C25n2」n-12」≥Z（5，n）+2n2」+3.

情形22crθ（∪4i=0Ti，En）=1，设crθ（Tx，En）=1，0≤x≤4.如图4，H中5个顶点都在圈Cn围成区域的内部分，除tx外的4个点满足引理26的条件，tx与圈上vj（1≤j≤n）的连边与圈Cn有一个交叉，若去掉边txvj则tx和圈内4个点与长为n-1的圈满足引理27的条件，即有

crθ（H∨Cn）≥crθ（∪4i=0Ti＼Tx）+crθ（∪4i=0Ti＼Tx，Tx）+crθ（∪4i=0Ti，En）≥

C24n2」n-12」+4n-12」n-22」+1≥Z（5，n）+2n2」+3.

情形23crθ（∪4i=0Ti，En）=2，分两种子情形.其中t1，t2，t3，t4的选取不影响下面的证明.

图3情形22crθ（∪4i=0Ti，En）=1

Fig.3Case 22 crθ（∪4i=0Ti，En）=1

图4情形23crθ（∪4i=0Ti，En）=2

Fig.4Case 23 crθ（∪4i=0Ti，En）=2

子情形231设crθ（Tx，En）=2，0≤x≤4，若与tx关联的一条边e与圈Cn发生两次交叉，则类似情形22可推出矛盾.若与tx关联的两条边e1，e2均为圈Cn发生交叉，如图4（a），H中除tx外的4个顶点满足引理27的条件，

crθ（H∨Cn）≥crθ（∪4i=0Ti＼Tx）+crθ（∪4i=0Ti＼Tx，Tx）+crθ（∪4i=0Tx，En）≥

C24n2」n-12」+4n-22」n-32」+1≥Z（5，n）+2n2」+3，n≥6.

子情形232crθ（Tx，En）=1且crθ（Ty，En）=1，0≤x≤y≤4如图4（b），与e1，e2关联且在圈上的端点是否相同不影响下面证明，H中5个顶点中除tx，ty外的3个点满足引理27的条件.

crθ（H∨Cn）≥crθ（∪4i=0Ti＼{Tx∪Ty}）+crθ（∪4i=0Ti＼{Tx∪Ty}，Tx∪Ty）+crθ（Tx∪Ty，En）≥

C23n2」n-12」+6n-12」n-22」+2≥Z（5，n）+2n2」+3，n≥6.

综上所述，假设不成立，即不存在H∨Cn的一个好画法θ，使得crθ（H∨Cn）≤Z（5，n）+2n2」+2，从而定理得证.

参考文献：

[1]BONDY J A， MURTY U S R. Graph theory with applications[M]. London： Macmilan， 1976.

[2]GAREY M R， JOHNSON D S. Crossing number is NPcomplete[J]. SIAM J Algebric Discrete Methods， 1993，4（3）：312316.

[3]KLEITMAN D J. The crossing number of K5，n[J]. Combin Theory， 1971，9（4）：315323.

[4]HO P T. On the crossing number of some complete multipartite graphs[J]. Utilitas Mathematica， 2009，29（2）：143154.

[5]HUANG Y Q， ZHAO T L. The crossing number of K1，4，n[J].Discrete Methods， 2008，308（9）：16341638.

[6]MEI H F， HUANG Y Q. The crossing number of K1，5，n[J].Int J Math Com， 2007，1（1）：3344.

[7]KLECˇ M. On the crossing number of Cartesian products of stars and paths or cycles[J]. Math Slovaca， 1991，41：113120.

[8]BEINEKE L W， RINGEISEN R D. On the crossing number of products of cycles and graphs of order four[J]. Graph Theory， 1980，4：145155.

[9]KLECˇ M. The crossing number of the Cartesian products of Wm with Pn[J].Math Resear， 2009，29（2）：362366.

[10]ZARANKIEWICZ K. On a problem of P.Turan concerning graphs[J].Fund Math， 1954，41（1）：137145.

[11]OPOROWSKI B， ZHAO D. Coloring graphs with crossing[J]. Discrete Math， 2009，309（9）：29482951.

[12]TANG L， WANG J， HUANG Y Q. The crossing number of the join of Cn and Pn[J].Int J Math Com， 2007，11：110116.

[13]KLECˇ M. The join of the graphs and crossing numbers[J].Electro Notes Discrete Math， 2007，28（1）：34935.

[14]王晶，黄元秋. Sm∨Pn与Sm∨Cn的交叉数[J].数学进展， 2011，40（5）：631636.

[15]苏振华，黄元秋.Wm∨Pn的交叉数[J].数学研究， 2012，45（3）：310314.

（编辑胡文杰）