聯(lián)圖K1,1,3∨Cn的交叉數(shù)

蘇振華

SU Zhenhua

懷化學(xué)院 數(shù)學(xué)系，湖南 懷化 418008

Department of Mathematics,Huaihua University,Huaihua,Hunan 418008,China

1 引言

圖G=(V(G),E(G))是簡(jiǎn)單連通圖。將一個(gè)圖G畫(huà)在平面上時(shí)，若滿(mǎn)足如下條件：

（1）任何兩條相交叉的邊最多交叉一次；

（2）邊不能自身交叉；

（3）有相同端點(diǎn)的兩條邊不交叉；

（4）沒(méi)有三條邊交叉于同一點(diǎn)。

則稱(chēng)此畫(huà)法為G的一個(gè)（好）畫(huà)法。若圖G的一個(gè)好畫(huà)法用D表示，G中所有邊與邊的交叉數(shù)稱(chēng)為在畫(huà)法D下G的交叉數(shù)，用crD(G)表示。圖G的交叉數(shù)，定義為cr(G)=minD{crD(G)}，其中最小值min取遍G的所有好畫(huà)法D。若存在G的一個(gè)好畫(huà)法φ滿(mǎn)足crφ(G)=cr(G)，則稱(chēng)φ為G的一個(gè)最優(yōu)畫(huà)法。本文未說(shuō)明的概念和術(shù)語(yǔ)均可參考文獻(xiàn)[1]。

圖的交叉數(shù)是圖的一個(gè)重要參數(shù)，研究圖的交叉數(shù)有重要的理論意義和現(xiàn)實(shí)意義。然而確定圖的交叉數(shù)是NP-完全問(wèn)題[2]。目前，只有少數(shù)圖類(lèi)的交叉數(shù)已經(jīng)確定[3-7]。1970年Kleitman得到了完全二部圖Km,n的交叉數(shù)的一個(gè)重要結(jié)果[4]：

兩個(gè)點(diǎn)不相交的圖G與H的聯(lián)圖，用G∨H表示，是在G與H的并圖中，把G的每個(gè)頂點(diǎn)與H的每個(gè)頂點(diǎn)連接起來(lái)所得到的圖。目前，關(guān)于聯(lián)圖的交叉數(shù)的研究。Oporowski等人在文獻(xiàn)[8]中得到了聯(lián)圖C3∨C6的交叉數(shù)。2007年Klesc[9]和唐玲[10]分別獨(dú)立地確定了聯(lián)圖 Pm∨Pn，Cm∨Pn，Cm∨Cn的交叉數(shù)。2010年Klesc[11]證明了一個(gè)特殊六階圖與路、圈的聯(lián)圖交叉數(shù)。2011年Klesc[12]得到了所有4階圖G 與路Pn，圈Cn的聯(lián)圖的交叉數(shù)，特別地得到了cr(K1,1,2∨Cn)=Z(4,n)+。袁秀華[13]研究了聯(lián)圖K2,3∨Cn的交叉數(shù)。文獻(xiàn)[14]得到了完全圖K1,1,3與路Pn的聯(lián)圖交叉數(shù)，并給出了目前已知的五階圖與路的聯(lián)圖交叉數(shù)結(jié)果。2014年岳為君等[15]得到了聯(lián)圖W4∨Cn的交叉數(shù)。

為與相關(guān)文獻(xiàn)保持一致，用Pn表示n個(gè)頂點(diǎn)的路，Cn表示長(zhǎng)為n的圈。本文在Klesc給出的聯(lián)圖K1,1,2∨Cn的交叉數(shù)為的基礎(chǔ)上，根據(jù)唐玲[10]和Klesc[11]得到的關(guān)于Cn聯(lián)圖交叉數(shù)的相關(guān)性質(zhì)，運(yùn)用反證法和排除法，得到了聯(lián)圖 K1,1,3∨Cn與{K1,1,3+e}∨Cn的交叉數(shù)均為

2 性質(zhì)與引理

性質(zhì)2.1[5]設(shè)D為圖G的一個(gè)好畫(huà)法。若A、B、C是圖G的三個(gè)互不相交的邊子集，則有：

性質(zhì)2.2[14]（1）若H 與G同構(gòu)，則cr(H)=cr(G)；

（2）若H 是G的子圖，則cr(H)≤cr(G)；

（3）設(shè)D是G的一個(gè)好畫(huà)法，則cr(G)≤crD(G)。

引理2.4[10]設(shè)G為任意圖，若D為圖G∨Cn的一個(gè)最優(yōu)畫(huà)法，則圈Cn自身不發(fā)生交叉，即crD(Cn)=0。

引理2.5[11]設(shè)D為圖mK1∨Cn的一個(gè)好畫(huà)法，若Cn自身不交叉，且不與其他邊交叉，若m個(gè)頂點(diǎn)位于圈Cn所形成的區(qū)域內(nèi)，則對(duì)所有的Ti與Tj(i≠j)，有

3 K1,1,3∨Cn的交叉數(shù)

為了方便，首先對(duì)K1,1,3∨Cn作如下標(biāo)記：V(K1,1,3∨Cn)={t1,t2,…,t5}?{v1,v2,…,vn}，Ti(1≤i≤5)為 K1,1,3的頂點(diǎn)ti與vj(1≤j≤n)相連邊的導(dǎo)出子圖。則有：

證明 當(dāng)n=3時(shí)，K1,1,3∨C3同構(gòu)于聯(lián)圖K5∨3K1，由引理2.1及性質(zhì)2.2可得：cr(K1,1,3∨C3)=cr(K5∨，結(jié)論成立。下面的證明僅需考慮n≥4的情形。

由圖1，K1,1,3∨Cn的一個(gè)好畫(huà)法，通過(guò)計(jì)數(shù)與性質(zhì)2.2可得。下面只需證明對(duì)任意的好畫(huà)法φ，均有成立即可?，F(xiàn)假設(shè)存在K1,1,3∨Cn的一個(gè)最優(yōu)畫(huà)法D，使得：

圖1 K1,1,3∨Cn的一個(gè)好畫(huà)法

斷言1圈Cn的每條邊最多有1個(gè)交叉。

否則若有2個(gè)交叉發(fā)生在Cn的同一邊上，則刪除Cn的這條邊，得到一個(gè)同構(gòu)于K1,1,3∨Pn的子圖，由性質(zhì) 2.1，2.2 及 引 理 2.3，有。與假設(shè)式（2）矛盾。

其次若。因?yàn)镵1,1,3為2-邊連通圖(crD(Cn,K1,1,3)≥2)，所以只可能是刪除Cn中與相交的那條邊，得到的圖同構(gòu)于K1,1,3∨Pn，因此有，與引理2.3矛盾。

下面根據(jù)斷言2分4種情形討論。

子情形1.1 K1,1,3的5個(gè)頂點(diǎn)均位于Cn的同一（內(nèi)部或外部）區(qū)域，且

子情形1.2 K1,1,3的1個(gè)2-度點(diǎn)，不妨設(shè)為t1，位于Cn的內(nèi)部區(qū)域，則K1,1,3的其余4個(gè)頂點(diǎn)均位于Cn的外部區(qū)域（如圖2（a）所示）。根據(jù)K1,1,3的結(jié)構(gòu)，存在連接t2、t3的邊，t1、t2、t3構(gòu)成3-圈，且 t1、t2、t3的兩交叉邊之間至少存在一個(gè)頂點(diǎn)v。因此

（1）若crD(K1,1,3)=0。則K1,1,3畫(huà)法唯一。因此在圖2（a）中，不論 t4、t5，位于 t1t2t3內(nèi)部或外部區(qū)域，均有crD(T4?T5,K1,1,3)≥4。因此有，與式（2）矛盾。

圖2 不同情況下Cn與發(fā)生的交叉圖

（2）若 crD(K1,1,3)≥1 。在圖2（a）中，不論 t4、t5，位于t1t2t3內(nèi)部或外部區(qū)域，均有crD(T4,K1,1,3)≥1,crD(T5,K1,1,3)≥1。因此有，與式（2）矛盾。

子情形2.1 K1,1,3的5個(gè)頂點(diǎn)均位于Cn的同一（內(nèi)部或外部）區(qū)域，且不妨設(shè)crD(Cn,T1)=1。對(duì)2≤i＜j≤5，根據(jù)引理2.5可得因此有。矛盾。

子情形2.2 K1,1,3的1個(gè)2-度點(diǎn)，不妨設(shè)為t1，位于Cn的內(nèi)部區(qū)域，其余4個(gè)頂點(diǎn)均位于Cn的外部區(qū)域（如圖2所示）。根據(jù) K1,1,3的結(jié)構(gòu)，存在t2、t3與t1構(gòu)成3-圈。

（1）若 crD(Cn,T1)=1。則Cn與 K1,1,3及T1發(fā)生3個(gè)交叉如圖2（b）所示。不論t4、t5，位于t1t2t3內(nèi)部或外部區(qū)域，均有crD(T4?T5,K1,1,3)≥2，crD(T4?T5,T1)≥2。因此有，矛盾。

（2）若 crD(Cn,T2)=1或 crD(Cn,T3)=1。不妨設(shè)crD(Cn,T2)=1。根據(jù)畫(huà)法的定義及斷言1，Cn與K1,1,3及T2發(fā)生的3個(gè)交叉如圖2（c）所示。則有1。因此有，矛盾。

（3）若crD(Cn,T4)=1或crD(Cn,T5)=1。不妨設(shè)crD(Cn,T4)=1 。若 t4位于 t1、t2、t3內(nèi)部區(qū)域，則 crD(T3,K1,1,3)≥1,crD(T4,K1,1,3)≥2，crD(T5,K1,1,3)≥2，crD(T1,T4)≥1。因此有，矛盾。

若 t4位于 t1、t2、t3外部區(qū)域，則交叉情況如圖2（d）所示。且根據(jù)圖K1,1,3的結(jié)構(gòu)，t2與t4之間有邊相連。則有crD(T1,T4)≥1,crD(T4,K1,1,3)≥1，crD(T3,K1,1,3?t4vi)≥1，若crD(K1,1,3)=0，則有crD(T5,K1,1,3?t4vi)≥3；若crD(K1,1,3)≥1，則crD(T5,K1,1,3?t4vi)≥2。因此總有：，矛盾。

子情形3.1存在一點(diǎn)，不妨設(shè)為t1，滿(mǎn)足crD(Cn,T1)=2。根據(jù)引理2.4，cr(Cn)=0。G的5個(gè)頂點(diǎn)全部位于Cn所分的一個(gè)（內(nèi)部或外部）區(qū)域內(nèi)，不妨設(shè)為外部區(qū)域。

（1）當(dāng)n=4時(shí)。根據(jù)畫(huà)法的的定義及斷言2.1，只能是T1的兩條邊與C4的兩條邊產(chǎn)生2個(gè)交叉（T1的一條邊與C4的兩條邊各產(chǎn)生1個(gè)交叉時(shí)，與畫(huà)法的定義矛盾），相關(guān)圖形如圖3（a）所示。顯然不論K1,1,3的另外4個(gè)頂點(diǎn)位于Cn外部的哪個(gè)區(qū)域，對(duì)2≤i≤5，有crD(Ti,T1)≥2。由引理2.5，對(duì)2≤i＜j≤5，有cr(Ti,Tj)≥因此，矛盾。

圖3 不同情況下Cn與發(fā)生的交叉圖

（2）當(dāng) n≥5時(shí)。由引理 2.5，對(duì) 2≤i＜j≤5，有。因此有。矛盾。

子情形3.2存在兩點(diǎn)，不妨設(shè)為t1、t2，滿(mǎn)足crD(Cn,T1)=crD(Cn,T2)=1。

Cn將平面分成內(nèi)外兩個(gè)區(qū)域，不妨設(shè)K1,1,3的5個(gè)頂點(diǎn)全部位于Cn的外部區(qū)域。根據(jù)畫(huà)法的定義及斷言1，只能是T1、T2分別與Cn的兩邊分別交叉，不妨設(shè)兩交叉點(diǎn)為 x1、x2，如圖3（b）所示。根據(jù) K1,1,3的構(gòu)造，任意兩個(gè)頂點(diǎn)t1、t2之間均有路連接，因此路t1t2把Cn的外部區(qū)域分成t1t2x2x1內(nèi)部和外部?jī)蓚€(gè)區(qū)域，不論K1,1,3的另外3個(gè)頂點(diǎn)位于哪個(gè)區(qū)域，對(duì)3≤i≤5，均有。對(duì)T1、T2，有。因此，矛盾。

子情形4.1存在一點(diǎn)，不妨設(shè)為t1，滿(mǎn)足crD(Cn,T1)=3。

根據(jù)畫(huà)法的定義及斷言1，T1與Cn產(chǎn)生3個(gè)交叉時(shí)，Cn至少有5個(gè)以上頂點(diǎn)（否則不滿(mǎn)足題設(shè)條件）。由引理5，對(duì)2≤i＜j≤5，有。因此，矛盾。

子情形4.2存在兩點(diǎn)，不妨設(shè)為t1、t2，滿(mǎn)足

根據(jù)畫(huà)法的定義及斷言1，T1、T2與Cn的交叉只可能如圖3（c）所示，且Cn至少有5個(gè)以上頂點(diǎn)。因?yàn)閮蓚€(gè)交叉之間至少有一個(gè)頂點(diǎn)，所以T1與Cn的兩個(gè)交叉之間至少存在一個(gè)點(diǎn)，則對(duì)3≤i＜j≤5，有cr(Ti,T1)≥。因此，矛盾。

子情形4.3存在3點(diǎn)，不妨設(shè)為t1、t2、t3，滿(mǎn)足

根據(jù)畫(huà)法的定義及斷言1，T1、T2、T3與 Cn的交叉只可能如圖3（d）所示，且Cn至少有5個(gè)以上頂點(diǎn)。因?yàn)槿我鈨蓚€(gè)頂點(diǎn)之間均有路相連，則t1、t2、t3之間均有路相連。對(duì)4≤i＜j≤5，不論ti位于哪個(gè)區(qū)域，均有cr(Ti,T1?且有因此4(n≥5)，矛盾。

綜合上述4種情形，假設(shè)式（2）不成立。因此對(duì)任意的好畫(huà)法 φ ，均有成立。定理得證。

4 {K1,1,3+e}∨Cn的交叉數(shù)

在圖K1,1,3，3個(gè)2-度點(diǎn)之間任意連接一邊e，可得到圖K1,1,3+e。有下面的定理。

證明 首先構(gòu)造{K1,1,3+e}+Cn的一個(gè)好畫(huà)法如圖4所示，顯然有其次根據(jù)K1,1,3+Cn?{K1,1,3+e}+Cn，則由定理3.1及性質(zhì)2.2可得。定理證畢。

圖4 {K1,1,3+e}+Cn的一個(gè)好畫(huà)法

5 結(jié)束語(yǔ)

本文在Klesc給出聯(lián)圖K1,1,2∨Cn的交叉數(shù)為Z(4,n)+的基礎(chǔ)上，根據(jù)聯(lián)圖的相關(guān)性質(zhì)，運(yùn)用反證法和排除法得到了聯(lián)圖K1,1,3∨Cn的交叉數(shù)為Z(5,n)+n+，并假設(shè)在Zarankiewicz猜想成立的前提下，根據(jù)本文的證明，給出了對(duì)K1,1,m∨Cn(m≥4)的交叉數(shù)的一個(gè)猜想：

長(zhǎng)期以來(lái)，計(jì)算圖的交叉數(shù)問(wèn)題研究主要采用純數(shù)學(xué)方法。但是，隨著所研究圖的階數(shù)增大，可能的畫(huà)法急劇增長(zhǎng)，研究也越來(lái)越困難，如對(duì)完全圖的研究，從n=10進(jìn)展到n=12，花了整整30年的時(shí)間。因此，隨著計(jì)算機(jī)技術(shù)突飛猛進(jìn)的發(fā)展，利用計(jì)算機(jī)輔助計(jì)算圖的交叉數(shù)是一種必然的趨勢(shì)。這也是各研究者今后一段時(shí)間內(nèi)面臨的極具挑戰(zhàn)性的工作。

參考文獻(xiàn)：

[1]Bondy J A，Murty U S R.Graph theory with applications[M].North-Holland：Elsevier Science Ltd，1976.

[2]Garey M R，Johnson D S.Crossing number is NP-complete[J].Slam J Algebric Discrete Methods，1993，4：312-316.

[3]黃元秋，王晶.圖的交叉數(shù)綜述[J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2010（3）：68-80.

[4]Kleitman D J.The crosing number ofK5,n[J].J Graph Series B，1970，9：315-323.

[5]Pak T H.The crossing number of K1,1,3,n[J].ARS Combinatoria，2011，99：461-471.

[6]Klesc M.The crossing number of Cartesian products of paths with 5-vertex graphs[J].Discrete Mathematics，2001，233：353-359.

[7]Lv S X，Huang Y Q.On the crossing numbers of K5×Sn[J].Journal of Mathematical Research Exposition，2008，28（3）：445-459.

[8]Oporowski B，Zhao D.Coloring graphs with crossing[J].Discrete Mathematics，2009，309：2948-2951.

[9]Klesc M.The join of graphs and crossing numbers[J].Electronic Notes in Discrete Math，2007，28：349-355.

[10]Tang Ling，Wang Jing，Huang Yuanqiu.The crossing numberofthejoin ofCmandPn[J].International Journal of Mathematical Combinatorics，2007，1：110-116.

[11]Klesc M.The crossing numbers of join of the special graph on six vertices with path and cycle[J].Discrete Mathematics，2010，310：1475-1481.

[12]Klesc M.The crossing numbers of join products of path with graphs of order four[J].Discussiones Mathematicae Gragh Theory，2011，31：321-331.

[13]袁秀華.K2,3∨Cn的交叉數(shù)[J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（5）：21-24.

[14]蘇振華，黃元秋.五階圖與路Pn的聯(lián)圖交叉數(shù)[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)，2014，29（2）：245-252.

[15]岳為君，黃元秋，歐陽(yáng)章東.聯(lián)圖W4∨Cn的交叉數(shù)[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（18）：79-84.