聯圖W4+Cn的交叉數

岳為君，黃元秋，歐陽章東

1.湖南師范大學數學與計算機科學學院，長沙 410081

2.湖南第一師范學院數學系，長沙 410205

聯圖W4+Cn的交叉數

岳為君1，黃元秋1，歐陽章東2

1.湖南師范大學數學與計算機科學學院，長沙 410081

2.湖南第一師范學院數學系，長沙 410205

1 引言

本文中未說明的概念和術語均同文獻[1]，且無特別說明所涉及的圖G=(V(G)，E(G))均指簡單連通圖，一個圖G在平面上的一個好畫法是指滿足以下四個條件的畫法：

（1）任意兩條邊最多交叉一次；（2）邊不能自身交叉；

（3）任意相鄰的兩條邊不能交叉；（4）沒有三條邊交叉于同一個點。

crD(G)表示在好畫法D下G中邊與邊之間的交叉數目。而圖G的交叉數，記為cr(G)，其中cr(G)=，即圖G的所有好畫法D中交叉數中的最小值。若φ是G的一個好畫法，使得crφ(G)=cr(G)，則稱φ是G的一個最優畫法。

圖的交叉數是圖的一個重要參數，自從圖的交叉數概念提出以來，國內外許多學者都做出了很多的研究，但由于確定圖的交叉數是NP-難問題[2]，目前國內外在確定圖類的交叉數研究中，主要是針對一些特殊結構的圖類上，或者一些圖與圖作某種運算后得到的圖，如完全2-部圖Km，n[3]，完全多部圖[4-5]一些路，以及星和圈與一些小階圖G的笛卡爾積圖[6-11]，特別地，關于完全2-部圖Km，n，1954年Zarankiewicz在文獻[12]中得到了著名的Zarankiewicz猜想，后來，Ringel和Kainen各自獨立發現Zarankiewicz在文獻[12]中的猜想有誤[13]。D.J.Kleitman在文獻[3]中證明了當min{m，n}≤6時，Zarankiewicz猜想成立，即Km，n的交叉數為：cr(Km，n)=Z(m，n)=。這里，對任意實數x，表示不超過x的最大整數。

令G和H是兩個沒有公共頂點的簡單圖，圖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)。

本文中，一個輪圖Wm是指一個圈Cm添加一個新頂點，并且把這個頂點與圈的所有頂點相連所得的圖，記號Cn表示有n個點的一個圈。目前，有關聯圖的交叉數方面的研究結果較少。Oporowski B等人在文獻[14]中得到了聯圖C3+C6的交叉數。文獻[15]已經確定了Pm+Pn和Cm+Cn的交叉數。近期，Klesc M在文獻[16]中，得到了所有3-階和4-階圖G與路Pn，圈Cn的聯圖的交叉數。本文主要確定了5-階輪圖W4的聯圖的交叉數，即如下定理：

定理1設W4為輪圖，圈Cn為一個長為n的圈，則有：

2 基本性質和引理

在證明本文主要結果之前，先給出如下一些基本性質和引理。首先，由交叉數的定義，易有如下性質：

性質2.1令D是圖G的一個好畫法，且A，B，C是圖G的三個邊不相交的子圖，則有：

（1）crD(A∪B)=crD(A)+crD(B)+crD(A，B)

（2）crD(A∪B，C)=crD(A，C)+crD(B，C)

性質2.2若A是G的子圖，則有cr(A)≤cr(G)。

性質2.3若圖G與圖H同構，則有cr(G)=cr(H)。

引理2.4[11]cr(K4，n)=Z(4，n)，cr(K5，n)=Z(5，n)。

引理2.5[15]設G為任意一個圖，φ是Cn+G的一個最優畫法，則圈Cn自身不會相交，即crφ(Cn)=0。

引理2.6[16]cr(W3+Cn)=Z(4，n)+n+4，n≥3。

下面的引理在本文第3章主要結果的證明中反復運用。

引理2.8設Cn=v1v2…vn為一個圈，Cn在平面上圍成一個圓盤D，在D的內部放置m個點xj(1≤j≤m)，xj與每個vi(1≤i≤n)連邊，記這樣的邊組成的集合為Txj。若φ是這樣一個畫法，使得所有邊集Txj都畫在圓盤D的內部，即產生的交叉數，即

3 定理的證明

定理3.1設W4為輪圖，圈Cn為一個長為n的圈，則有

在證明定理之前，為了方便，先規定有關記號：設V(W4)={t0，t1，t2，t3，t4}，其中t0是W4的中心點，而ti(1≤i≤4)表示W4的葉子點；V(Cn)={v1，v2，…，vn}，En=E(Cn)；對每個0≤i≤4，記T=T0∪T1∪T2∪T3∪T4，其中Ti={tivj|1≤j≤n}。E′0={t0ti|1≤i≤4}，C4=t1-t2-t3-t4-t1，E(C4)=E′4，則E(W4)=E′0∪E′4。又對于G+Cn的任意邊子集A，A表示由G+Cn的邊子集A導出的子圖。于是W4+Cn的邊集可分解為如下一些不相交的邊子集的并，即有

因此，在后面的證明中，總是假定n≥4。

先在平面上構造W4+Cn的一個好畫法π，使

畫法π的構造如圖1。

圖1 W4+Cn的一個好畫法π

以下證明在畫法φ下總能得到一個與式（1）相矛盾的結論，從而得到假設不成立。

在以下的證明，總是記住如下事實及斷言：

事實因為φ是最優畫法，由引理2.5可知，Cn自身不會交叉，即crφ(En)=0。在畫法φ下，Cn圍成一個圓盤D，由對稱性，可以假定點t0總是位于圓盤D的內部。

斷言1在φ是W4+Cn最優畫法下，crφ(E′4，En)+

證明根據引理2.7和性質2.1以及事實可得：

圖2 W4的兩種特殊情形

子情形1.1當crφ(E′4，En)=0且crφ(E′0，En)≤3時，W4的5個頂點都在Cn的同一區域，且所有邊集Txj，0≤j≤4都畫在圓盤D的內部，由引理2.8得：

子情形1.2當crφ(E′4，En)=2且crφ(E′0，En)≤1時。

子情形1.2.1當crφ(E′4，En)=2且crφ(E′0，En)=0時，如圖3，W4的5個頂點都在Cn的同一區域，且所有邊集Txj，0≤j≤4都畫在圓盤D的內部，由引理2.8得：

圖3 子情形1.2.1

子情形1.2.2當crφ(E′4，En)=2且crφ(E′0，En)=1時，如圖4（a）。

圖4 子情形1.2.2

（1）若W4自身有交叉，即crφ(W4)≥1，W4+Cn包含一個K4，n+1子圖，則：

（2）若W4自身無交叉，設Cn有x1個頂點在C4外部，x2個頂點在C4內部，其中x1+x2=n。在最優畫法φ下W4+Cn包含一個邊導出子圖W3+Cn，且crφ(C3，Cn)=2，其中C3=t1-t2-t3-t1。W3的四個頂點全在Cn內部，C3和不自交的Cn有兩個交叉只有如圖4（b）一種情況，C3把Cn內部分成兩個對稱區域，若t0在圈C3內部，則t2在圈t1-t0-t3-t1外部，記圈t1-t0-t3-t1為C，若t0在圈C3外部，則t2在圈C內部，由Jordan曲線定理可知crφ(T0，C3)+crφ(T2，C)≥n，由性質2.2知：

圖5 情形2

子情形2.2當crφ(E′4，En)=2時，則crφ(E′0，En)=0如圖5（b），記crφ(Tx，En)=1，0≤x≤4。又，W4的四個頂點都在Cn的同一區域，且四個點的所有邊集Tx都畫在圓盤D的內部，類似子情形2.1易推出與假設矛盾。

子情形3.1當crφ(Tx，En)=2，0≤x≤4時，滿足結論要求，如圖6。

圖6 子情形3.1

子情形3.1.1如圖6（a），由子情形2.1可得出與假設矛盾。

子情形3.1.2如圖6（b），

圖7 子情形3.2

子情形4.1當crφ(Tx，En)=3時，

子情形4.1.1如圖8（a），由子情形2.1可得出與假設矛盾。

圖8 子情形4.1

子情形4.1.2如圖8（b），由子情形3.1.2可得出與假設矛盾。

子情形4.1.3如圖8（c），

圖9 子情形4.2

子情形4.2.1如圖9（a），類似子情形3.2可推出與假設矛盾。

子情形4.2.2如圖9（b）。

子情形4.2.2.1當crφ(T0,En)=0時，不妨設crφ(T1,En)= 2，crφ(T2，En)=1，則

子情形4.2.2.2當crφ(T0，En)=1，類似子情形4.2.2.1可得出矛盾。

圖10 子情形4.3

4 結論及猜想

[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]Kleitman D J.The crossing number ofK5，n[J].Combinatorial Theory，1971，9：315-323.

[4]Ho P T.On the crossing number of some complete multipartite graphs[J].Utilitas Mathematica，2009，79：143-154.

[5]Mei H F，Huang Y Q.The crossing number ofK1，5，n[J]. International J Math Com，2007，1：33-44.

[6]Klesc M.The crossing numbers ofK2，3×PnandK2，3×Sn[J].Tatra Moutains Math Publ，1996，1：51-56.

[7]Klesc M.On the crossing number of Cartesian products of stars and paths or cycles[J].Math Slovaca，1991，41：113-120.

[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：145-155.

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

[10]Klesc M.The crossing number of the Cartesian products ofWmwithPn[J].Mathematical Research，2009，29：362-366.

[11]Wang J，Huang Y Q.The crossing number ofK2，4×Pn[J]. Acta Mathematica Scientia：in Chinese，2008，28A：251-255.

[12]Zarankiewicz K.On a problem of P.turan concerning graphs[J].Fund Math，1954，41：137-145.

[13]Guy R K.The decline and fall of Zarankiewicz’s theorem[C]//Proc of the Second Ann Arbor Graph Theory Conference.New York：Academic Press，1969：63-69.

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

[15]Tang L，Wang J，Huang Y Q.The crossing number of the join ofCnandPn[J].International J Math Com，2007，11：110-116.

[16]Klesc M.The join of the graphs and crossing numbers[J]. Discrete Math，2007，28：349-355.

[17]賀佩玲，黃元秋.W4×Sn的交叉數[J].鄭州大學學報：理學版，2007，39（4）：14-21.

YUE Weijun1,HUANG Yuanqiu1,OUYANG Zhangdong2

1.College of Mathematics and Computer Science,Hunan Normal University,Changsha 410081,China
2.Department of Mathematics,Hunan First Normal University,Changsha 410205,China

drawing;crossing number;join graph;Cn

聯圖G+H表示將G中每個點與H中的每個點連邊得到的圖。在Klesc M.給出聯圖W3+Cn的交叉數的基礎上，應用反證法和排除法得到了聯圖W4+Cn的交叉數為，并在Zarankiewicz猜想成立的前提下，根據證明，提出對Wm+Cn的交叉數的一個猜想：

畫法；交叉數；聯圖；圈

A

O157.5

10.3778/j.issn.1002-8331.1401-0203

YUE Weijun,HUANG Yuanqiu,OUYANG Zhangdong.On crossing numbers of join ofW4+Cn.Computer Engineering and Applications,2014,50（18）：79-84.

國家自然科學基金（No.11371133，No.11301169）。

岳為君（1989—），男，碩士，主要研究方向：圖論及其應用；黃元秋（1966—），通訊作者，男，博士，教授，博士生導師，主要研究方向：圖論及其應用；歐陽章東（1981—），男，博士，講師，主要研究方向：圖論及其應用。E-mail：hyqq@hunnu.edu.cn

2014-01-14

2014-03-18

1002-8331（2014）18-0079-06