一個特殊5—階圖與圈Cn的聯(lián)圖的交叉數(shù)

岳為君 黃元秋

摘要 聯(lián)圖G∨H表示將G中每個點與H中的每個點連邊得到的圖.在Klecˇ給出所有3階圖和4階圖與圈Cn的聯(lián)圖的交叉數(shù)的基礎上，確定了一個5階圖與圈Cn的聯(lián)圖的交叉數(shù).

關鍵詞畫法；交叉數(shù)；聯(lián)圖；圈

中圖分類號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中邊與邊之間的交叉數(shù)目.而圖G的交叉數(shù)，記為cr（G），是指這樣一個值：cr（G）=minD{crD（G）}，其中D取遍G的所有好畫法.若D是G的一個好畫法，使得crD（G）=cr（G），則稱D是G的一個最優(yōu)畫法.

圖的交叉數(shù)是圖的一個重要參數(shù)，自從圖的交叉數(shù)概念提出以來，國內外許多學者都做出了很多的研究.但由于確定圖的交叉數(shù)是NP問題[2]，至今在確定圖類的交叉數(shù)研究中，主要是針對一些具有特殊結構的圖類，如完全2部圖Km，n[3]，完全多部圖[46]，或者一些圖與圖作某種運算后得到的圖，如路或圈與一些低階圖的笛卡爾積圖[79].特別地，關于完全2部圖Km，n，Kleitman在文獻[3]中證明了當min{m，n}≤6時，Zarankiewicz猜想[10]成立，即Km，n的交叉數(shù)為：cr（Km，n）=Z（m，n）=m2」m-12」n2」n-12」（min{m，n}≤6），這里，對任意實數(shù)x，x」表示不超過x的最大整數(shù).

設G和H是兩個無公共頂點的簡單圖，聯(lián)圖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中的邊之間產生的交叉數(shù)；記號cr（A，B）表示在畫法下，A中邊與B中的邊之間產生的交叉數(shù).顯然，當A=E（G）時，cr（A）=cr（G）.

圖1H的一個好畫法

Fig.1A good illustration of H

目前，有關聯(lián)圖的交叉數(shù)方面的研究結果較少.Oporowski在文獻[11]中確定了C3∨C6的交叉數(shù).文獻[12]確定了Pm∨Pn，Pm∨Cn和Cm∨Cn的交叉數(shù).Klecˇ在文獻[13]中，得到了所有3階、4階圖G與路Pn與圈Cn的聯(lián)圖的交叉數(shù).文獻[14]確定了當m=，3，4，5時Sm∨Pn的交叉數(shù)，以及m=3，4時Sm∨Cn的交叉數(shù).本文中Pn和Cn分別表示長為n的路，長為n的圈.Sn表示星圖K1，n.

設H是如圖1所示的一個5階圖，是文獻[14]中的S4加3條邊得到的，E（H）=E（S4）∪{t1t2，t2t3，t3t4}.

本文確定了H與圈Cn的聯(lián)圖的交叉數(shù)，主要結果如下：

定理設H是如圖1所示的一個5階圖，Cn（n≥3）表示長為n的圈，則有

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

1基本性質和引理

在證明本文的主要結果之前，先給出一些基本性質和引理.

首先，由交叉數(shù)的定義，易有如下性質：

性質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的一個最優(yōu)畫法，則圈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在畫法產生的交叉數(shù)，滿足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定理的證明

先規(guī)定有關記號：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，根據(jù)性質23和引理25，

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

當n=4時，H∨C4同構于W4∨P4，根據(jù)性質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，根據(jù)性質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）從原點出發(fā)把v1，v2，…，vn2」從左至右依次放置在x的正半軸上；

（2）從原點出發(fā)把vn，vn-1，…，vn2」從右至左依次放置在x軸的負半軸上；

（3）點t2，t1依次放置在y軸的正半軸上，點t4，t3依次放置在y軸的負半軸上，t0放置在點（ε，ε）位置上，這里ε是很小的正數(shù)；

圖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的一個最優(yōu)畫法[3].根據(jù)引理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的一個好畫法θ，不妨設θ是最優(yōu)畫法，使得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，根據(jù)性質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根據(jù)性質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.根據(jù)性質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的同一區(qū)域，又由斷言22 crθ（E0，En）≤2，如果t0與t1，t2，t3，t4不在同一區(qū)域，則crθ（E0，En）≥4，所以H的5個頂點都在同一區(qū)域，且crθ（E0，En）=0或者crθ（E0，En）=2.由引理23知Cn把平面分成2個區(qū)域，不妨設H的5個頂點都在Cn圍成區(qū)域的內部.

在下面的討論中，我們在不計算crθ（E0，En）的情況下，就能得到H∨Cn最優(yōu)畫法θ下的交叉數(shù)與（*）式矛盾.即crθ（E0，En）=0或crθ（E0，En）=2不影響我們的計算結果，不妨設crθ（E0，En）=0.

根據(jù)斷言22可知crθ（∪4i=0Ti，En）≤2，下面分3種情形進行討論：

情形21crθ（∪4i=0Ti，En）=0，H中5個頂點都滿足引理27的條件，根據(jù)引理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圍成區(qū)域的內部分，除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關聯(lián)的一條邊e與圈Cn發(fā)生兩次交叉，則類似情形22可推出矛盾.若與tx關聯(lián)的兩條邊e1，e2均為圈Cn發(fā)生交叉，如圖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關聯(lián)且在圈上的端點是否相同不影響下面證明，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的交叉數(shù)[J].數(shù)學進展， 2011，40（5）：631636.

[15]蘇振華，黃元秋.Wm∨Pn的交叉數(shù)[J].數(shù)學研究， 2012，45（3）：310314.

（編輯胡文杰）