聯(lián)圖W4+Cn的交叉數(shù)

岳為君，黃元秋，歐陽(yáng)章東

1.湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，長(zhǎng)沙 410081

2.湖南第一師范學(xué)院數(shù)學(xué)系，長(zhǎng)沙 410205

聯(lián)圖W4+Cn的交叉數(shù)

岳為君1，黃元秋1，歐陽(yáng)章東2

1.湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，長(zhǎng)沙 410081

2.湖南第一師范學(xué)院數(shù)學(xué)系，長(zhǎng)沙 410205

1 引言

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

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

（3）任意相鄰的兩條邊不能交叉；（4）沒有三條邊交叉于同一個(gè)點(diǎn)。

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

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

令G和H是兩個(gè)沒有公共頂點(diǎn)的簡(jiǎn)單圖，圖G和H的聯(lián)圖G+H表示這樣的一個(gè)圖：頂點(diǎn)集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)表示連接頂點(diǎn)u和v的邊。設(shè)φ是圖G的一個(gè)好畫法，對(duì)G的任意邊子集A和B，記號(hào)crφ(A)表示在畫法φ下，A中邊之間產(chǎn)生的交叉數(shù)：記號(hào)crφ(A，B)表示在畫法φ下，A中邊與B中的邊之間產(chǎn)生的交叉數(shù)。顯然，當(dāng)A=E(G)時(shí)，crφ(A)=crφ(G)。

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

定理1設(shè)W4為輪圖，圈Cn為一個(gè)長(zhǎng)為n的圈，則有：

2 基本性質(zhì)和引理

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

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

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

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

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

性質(zhì)2.3若圖G與圖H同構(gòu)，則有cr(G)=cr(H)。

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

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

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

下面的引理在本文第3章主要結(jié)果的證明中反復(fù)運(yùn)用。

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

3 定理的證明

定理3.1設(shè)W4為輪圖，圈Cn為一個(gè)長(zhǎng)為n的圈，則有

在證明定理之前，為了方便，先規(guī)定有關(guān)記號(hào)：設(shè)V(W4)={t0，t1，t2，t3，t4}，其中t0是W4的中心點(diǎn)，而ti(1≤i≤4)表示W(wǎng)4的葉子點(diǎn)；V(Cn)={v1，v2，…，vn}，En=E(Cn)；對(duì)每個(gè)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。又對(duì)于G+Cn的任意邊子集A，A表示由G+Cn的邊子集A導(dǎo)出的子圖。于是W4+Cn的邊集可分解為如下一些不相交的邊子集的并，即有

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

先在平面上構(gòu)造W4+Cn的一個(gè)好畫法π，使

畫法π的構(gòu)造如圖1。

圖1 W4+Cn的一個(gè)好畫法π

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

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

事實(shí)因?yàn)棣帐亲顑?yōu)畫法，由引理2.5可知，Cn自身不會(huì)交叉，即crφ(En)=0。在畫法φ下，Cn圍成一個(gè)圓盤D，由對(duì)稱性，可以假定點(diǎn)t0總是位于圓盤D的內(nèi)部。

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

證明根據(jù)引理2.7和性質(zhì)2.1以及事實(shí)可得：

圖2 W4的兩種特殊情形

子情形1.1當(dāng)crφ(E′4，En)=0且crφ(E′0，En)≤3時(shí)，W4的5個(gè)頂點(diǎn)都在Cn的同一區(qū)域，且所有邊集Txj，0≤j≤4都畫在圓盤D的內(nèi)部，由引理2.8得：

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

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

圖3 子情形1.2.1

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

圖4 子情形1.2.2

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

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

圖5 情形2

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

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

圖6 子情形3.1

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

子情形3.1.2如圖6（b），

圖7 子情形3.2

子情形4.1當(dāng)crφ(Tx，En)=3時(shí)，

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

圖8 子情形4.1

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

子情形4.1.3如圖8（c），

圖9 子情形4.2

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

子情形4.2.2如圖9（b）。

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

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

圖10 子情形4.3

4 結(jié)論及猜想

[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的交叉數(shù)[J].鄭州大學(xué)學(xué)報(bào)：理學(xué)版，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

聯(lián)圖G+H表示將G中每個(gè)點(diǎn)與H中的每個(gè)點(diǎn)連邊得到的圖。在Klesc M.給出聯(lián)圖W3+Cn的交叉數(shù)的基礎(chǔ)上，應(yīng)用反證法和排除法得到了聯(lián)圖W4+Cn的交叉數(shù)為，并在Zarankiewicz猜想成立的前提下，根據(jù)證明，提出對(duì)Wm+Cn的交叉數(shù)的一個(gè)猜想：

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

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.

國(guó)家自然科學(xué)基金（No.11371133，No.11301169）。

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

2014-01-14

2014-03-18

1002-8331（2014）18-0079-06