聯圖K1,1,3∨Cn的交叉數

蘇振華

SU Zhenhua

懷化學院 數學系，湖南 懷化 418008

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

1 引言

圖G=(V(G),E(G))是簡單連通圖。將一個圖G畫在平面上時，若滿足如下條件：

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

（2）邊不能自身交叉；

（3）有相同端點的兩條邊不交叉；

（4）沒有三條邊交叉于同一點。

則稱此畫法為G的一個（好）畫法。若圖G的一個好畫法用D表示，G中所有邊與邊的交叉數稱為在畫法D下G的交叉數，用crD(G)表示。圖G的交叉數，定義為cr(G)=minD{crD(G)}，其中最小值min取遍G的所有好畫法D。若存在G的一個好畫法φ滿足crφ(G)=cr(G)，則稱φ為G的一個最優畫法。本文未說明的概念和術語均可參考文獻[1]。

圖的交叉數是圖的一個重要參數，研究圖的交叉數有重要的理論意義和現實意義。然而確定圖的交叉數是NP-完全問題[2]。目前，只有少數圖類的交叉數已經確定[3-7]。1970年Kleitman得到了完全二部圖Km,n的交叉數的一個重要結果[4]：

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

為與相關文獻保持一致，用Pn表示n個頂點的路，Cn表示長為n的圈。本文在Klesc給出的聯圖K1,1,2∨Cn的交叉數為的基礎上，根據唐玲[10]和Klesc[11]得到的關于Cn聯圖交叉數的相關性質，運用反證法和排除法，得到了聯圖 K1,1,3∨Cn與{K1,1,3+e}∨Cn的交叉數均為

2 性質與引理

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

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

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

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

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

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

3 K1,1,3∨Cn的交叉數

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

證明 當n=3時，K1,1,3∨C3同構于聯圖K5∨3K1，由引理2.1及性質2.2可得：cr(K1,1,3∨C3)=cr(K5∨，結論成立。下面的證明僅需考慮n≥4的情形。

由圖1，K1,1,3∨Cn的一個好畫法，通過計數與性質2.2可得。下面只需證明對任意的好畫法φ，均有成立即可。現假設存在K1,1,3∨Cn的一個最優畫法D，使得：

圖1 K1,1,3∨Cn的一個好畫法

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

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

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

下面根據斷言2分4種情形討論。

子情形1.1 K1,1,3的5個頂點均位于Cn的同一（內部或外部）區域，且

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

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

圖2 不同情況下Cn與發生的交叉圖

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

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

子情形2.2 K1,1,3的1個2-度點，不妨設為t1，位于Cn的內部區域，其余4個頂點均位于Cn的外部區域（如圖2所示）。根據 K1,1,3的結構，存在t2、t3與t1構成3-圈。

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

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

（3）若crD(Cn,T4)=1或crD(Cn,T5)=1。不妨設crD(Cn,T4)=1 。若 t4位于 t1、t2、t3內部區域，則 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外部區域，則交叉情況如圖2（d）所示。且根據圖K1,1,3的結構，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存在一點，不妨設為t1，滿足crD(Cn,T1)=2。根據引理2.4，cr(Cn)=0。G的5個頂點全部位于Cn所分的一個（內部或外部）區域內，不妨設為外部區域。

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

圖3 不同情況下Cn與發生的交叉圖

（2）當 n≥5時。由引理 2.5，對 2≤i＜j≤5，有。因此有。矛盾。

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

Cn將平面分成內外兩個區域，不妨設K1,1,3的5個頂點全部位于Cn的外部區域。根據畫法的定義及斷言1，只能是T1、T2分別與Cn的兩邊分別交叉，不妨設兩交叉點為 x1、x2，如圖3（b）所示。根據 K1,1,3的構造，任意兩個頂點t1、t2之間均有路連接，因此路t1t2把Cn的外部區域分成t1t2x2x1內部和外部兩個區域，不論K1,1,3的另外3個頂點位于哪個區域，對3≤i≤5，均有。對T1、T2，有。因此，矛盾。

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

根據畫法的定義及斷言1，T1與Cn產生3個交叉時，Cn至少有5個以上頂點（否則不滿足題設條件）。由引理5，對2≤i＜j≤5，有。因此，矛盾。

子情形4.2存在兩點，不妨設為t1、t2，滿足

根據畫法的定義及斷言1，T1、T2與Cn的交叉只可能如圖3（c）所示，且Cn至少有5個以上頂點。因為兩個交叉之間至少有一個頂點，所以T1與Cn的兩個交叉之間至少存在一個點，則對3≤i＜j≤5，有cr(Ti,T1)≥。因此，矛盾。

子情形4.3存在3點，不妨設為t1、t2、t3，滿足

根據畫法的定義及斷言1，T1、T2、T3與 Cn的交叉只可能如圖3（d）所示，且Cn至少有5個以上頂點。因為任意兩個頂點之間均有路相連，則t1、t2、t3之間均有路相連。對4≤i＜j≤5，不論ti位于哪個區域，均有cr(Ti,T1?且有因此4(n≥5)，矛盾。

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

4 {K1,1,3+e}∨Cn的交叉數

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

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

圖4 {K1,1,3+e}+Cn的一個好畫法

5 結束語

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

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

參考文獻：

[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]黃元秋，王晶.圖的交叉數綜述[J].華東師范大學學報：自然科學版，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的交叉數[J].華東師范大學學報：自然科學版，2011（5）：21-24.

[14]蘇振華，黃元秋.五階圖與路Pn的聯圖交叉數[J].高校應用數學學報，2014，29（2）：245-252.

[15]岳為君，黃元秋，歐陽章東.聯圖W4∨Cn的交叉數[J].計算機工程與應用，2014，50（18）：79-84.