圓有向圖的(1,2)步競(jìng)爭(zhēng)圖中存在哈密爾頓圈的條件

崔 建，葉 旺

(1.山西醫(yī)科大學(xué)汾陽(yáng)學(xué)院 基礎(chǔ)醫(yī)學(xué)部，山西 呂梁 032200; 2.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，太原 030000)

圓有向圖的(1,2)步競(jìng)爭(zhēng)圖中存在哈密爾頓圈的條件

崔 建1，葉 旺2

(1.山西醫(yī)科大學(xué)汾陽(yáng)學(xué)院 基礎(chǔ)醫(yī)學(xué)部，山西 呂梁 032200; 2.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，太原 030000)

針對(duì)圓有向圖的(1,2)步競(jìng)爭(zhēng)圖的結(jié)構(gòu)，提出了競(jìng)爭(zhēng)圖中是否存在哈密爾頓圈；通過(guò)特殊到一般的方法得到如下結(jié)論：對(duì)于階數(shù)n(n≥5)的強(qiáng)連通圓有向圖的(1,2)步競(jìng)爭(zhēng)圖中存在哈密爾頓圈，而其余情形的圓有向圖的(1,2)步競(jìng)爭(zhēng)圖中則不存在哈密爾頓圈。

圓有向圖；(1,2)步競(jìng)爭(zhēng)圖；哈密爾頓圈

0 引 言

1968年美國(guó)著名分子生物學(xué)家Cohen，首先提出了競(jìng)爭(zhēng)圖的概念，指出生態(tài)系統(tǒng)中的食物鏈和食物網(wǎng)都可以看作有向圖，其中的所有物種可看作頂點(diǎn)集，u到v有一條有向弧當(dāng)且僅當(dāng)物種u以物種v為食物。若物種x和物種y同時(shí)以物種z為食物，則x與y競(jìng)爭(zhēng)。競(jìng)爭(zhēng)圖除了被應(yīng)用在生態(tài)系統(tǒng)上外，在無(wú)線(xiàn)電廣播研究，噪聲信通道信研究及編碼理論等方面也被廣泛應(yīng)用[1]。自Cohen提出競(jìng)爭(zhēng)圖后，很多衍生概念陸續(xù)被人們提出，Lundgren等人[2]提出了公敵圖的概念；Cho等人[3]提出了m- 步競(jìng)爭(zhēng)圖的概念；Lundgren和Merz[4]提出了控制圖的概念；Factor和Merz[5]提出了(1,2)步競(jìng)爭(zhēng)圖及(i,k)步競(jìng)爭(zhēng)圖的概念，并完全刻畫(huà)了競(jìng)賽圖(1,2)步競(jìng)爭(zhēng)及(i,k)步競(jìng)爭(zhēng)圖的結(jié)構(gòu)。本文擬研究圓的有向圖的(1,2)步競(jìng)爭(zhēng)圖中存在的哈密爾頓圈的條件。

如果xy∈A(D)或者yx∈A(D)，那么x和y是相鄰。如果n個(gè)頂點(diǎn)的有向圖D的頂點(diǎn)可標(biāo)號(hào)為v0,v1，…，vn-1使得對(duì)每個(gè)i，總有N+(vi)={vi+1,vi+2,…，vi+d+(vi)}和N-(vi)={vi-d-(vi),vi-(vi)+1,…，vi-1}(所有下標(biāo)均取模n，以后不再重復(fù)說(shuō)明)，稱(chēng)D是圓有向圖，稱(chēng)序是v0,v1，…，vn-1。

有向圖D=(V,A)，對(duì)于每個(gè)X?V且X≤k-1，如果D-X是強(qiáng)連通的，則D是k強(qiáng)連通的，簡(jiǎn)稱(chēng)D是k強(qiáng)的。如果D是k(k≥2)強(qiáng)的，那么D也是k-1強(qiáng)的。

設(shè)D是一個(gè)圓有向圖，v0,v1,…,vn-1是圓有向圖D的一個(gè)圓坐標(biāo)，連續(xù)的頂點(diǎn)集{va,va+1,…，va+b}(其中a∈{0,1…,n-1},b>1)在D中構(gòu)成一個(gè)扁條，記住B，如果這些頂點(diǎn)滿(mǎn)足式(1)(2)(3)：

d+(va)=…=d+(va+b-2)=2

(1)

d-(va+2)=…=d-(va+b)=2

(2)

d-(va+1)=…=d+(va+b-1)=1

(3)

圖以及它的競(jìng)爭(zhēng)圖和(1，2)步競(jìng)爭(zhēng)圖Fig.1 ，the competition graph C()and the step (1, 2) competition graph

顯然，va,va+b在D中是割點(diǎn)，至少有一個(gè)割點(diǎn)的圓有向圖D總是可以刪去一些出度大于3的頂點(diǎn)和入度大于3的頂點(diǎn)之間的狐，得到一些扁條，這些扁條的并構(gòu)成的圓有向圖，記作D′。圖2(a)是下標(biāo)a=0,b=5的扁條B，圖2(b)(c)分別是該扁條B的競(jìng)爭(zhēng)圖和(1,2)步競(jìng)爭(zhēng)圖。

設(shè)G=(V,E)是一個(gè)無(wú)向圖，V是G的頂點(diǎn)集，E是G的邊集，包含G中的每個(gè)頂點(diǎn)的圈叫作G的哈密爾頓圈。

設(shè)D=(V,A)是一個(gè)有向圈，D=(V,E)是一個(gè)無(wú)向圈。如果無(wú)向圖G=(V,E)滿(mǎn)足,V(G)=V(D)并且xy∈E(G)，當(dāng)且僅當(dāng)D中存在頂點(diǎn)z≠x,y使得dD-y(x,z)=1,dD-x(y,z)=1,那么稱(chēng)G為D的競(jìng)爭(zhēng)圖，記為C(D)。

設(shè)T是l個(gè)頂點(diǎn)的競(jìng)賽圖，稱(chēng)D=T(S1,S2,…,Sl)是T的擴(kuò)充競(jìng)賽圖，C1,2(T)是T的(1,2)步競(jìng)爭(zhēng)圖，并稱(chēng)H=C1,2(T)[S1,S2,…,Sl]是D的同等擴(kuò)充。

圖2 a=0,b=5的扁條B以及它的競(jìng)爭(zhēng)圖C(B)和(1，2)步競(jìng)爭(zhēng)圖C1,2(B)Fig.2 The flat bar whena=0,b=5，the competition graph C(B)，and the step (1, 2) competition graphC1,2(B)

此外，研究強(qiáng)連通圓有向圖的競(jìng)爭(zhēng)圖及有向圖的(1,2)步競(jìng)爭(zhēng)圖中存在哈密爾頓圈的條件。

1 準(zhǔn)備知識(shí)

引理1D是一個(gè)有向圖，D′是D的子有向圖，則C(D′)?C(D)。

由引理1，可得到推論1。

推論1D是一個(gè)有向圖，D′是D的子有向圖，則C1,2(D′)?C1,2(D)。

由競(jìng)爭(zhēng)圖和(1,2)步競(jìng)爭(zhēng)圖的定義，顯然有以下的引理。

引理3x是有向圖D的一個(gè)頂點(diǎn)，則N-(x)誘導(dǎo)出C(D)的完全子圖。

引理4D是一個(gè)有向圖，C(D)是D的競(jìng)爭(zhēng)圖，C1,2(D)是D的(1,2)步競(jìng)爭(zhēng)圖，則C(D)?C1,2(D)。

2 存在哈密爾頓圈的條件分析之一

定理1 若D是一個(gè)n階的2強(qiáng)連通的圓有向圖，則C(D)中存在哈密爾頓圈。

推論2 若D是一個(gè)n階的2強(qiáng)以上的圓有向圖，則C(D)中存在哈密爾頓圈。

定理2 設(shè)D是一個(gè)n階的1強(qiáng)連通的圓有向圖，且D中只有一個(gè)割點(diǎn)記作vi。若D中的頂點(diǎn)滿(mǎn)足d-(vi+j)≥3(j≠1,2)，則C(D)中存在哈密爾頓圈。

證明不妨設(shè)v0是階為n的1強(qiáng)連通圓有向圖D的割點(diǎn)，由d-(vj)=d-(v0+j)≥3(j≠1,2)，得{vj-3vj-2vj-1}?N-(vj)(j≠1,2)。由引理2.4，{vj-3vj-2vj-1}(j≠1,2)構(gòu)成的完全圖是C(D)的子圖。

當(dāng)n是奇數(shù)時(shí)，v0v2v4…vn-1vn-2vn-4…v3v1v0在C(D)中是哈密爾頓圈;當(dāng)n是偶數(shù)時(shí)，v0v2v4…

vn-2vn-1vn-3…v3v1v0在C(D)中是哈密爾頓圈。再由引理2，命題得證。

根據(jù)上面的證明，猜想下面的結(jié)論是正確的。

猜想1 若強(qiáng)連通圓有向圖D中有k(0

3 存在哈密爾頓圈的條件分析之二

定理3 若D是n階的2強(qiáng)以上的圓有向圖，則C1,2(D)中存在哈密爾頓圈。

當(dāng)D是一個(gè)n階的1強(qiáng)的圓有向圖時(shí)，考慮C1,2(D)中是否存在哈密爾頓圈。若C1,2(D)中存在哈密爾頓圈，D應(yīng)該滿(mǎn)足什么樣的條件。

引理5 若vi是1強(qiáng)的圓有向圖D中的割點(diǎn)，則d+(vi-1)=1且d-(vi+1)=1。反之也成立。

引理6 設(shè)連續(xù)的頂點(diǎn)集{va，va+1,…,va+b}(其中a∈{0,1,…,n-1},b>1)在圓有向圖D中構(gòu)成一個(gè)扁條B，則C1,2(B)是由以下幾種無(wú)向圖構(gòu)成：

定理4 若n(n≥5)階的1強(qiáng)連通有向圖D中下標(biāo)相鄰的頂點(diǎn)不同時(shí)是割點(diǎn)，則C1,2(D)中存在哈密爾頓圈。

證明情形1：圓有向圖D中只有一個(gè)割點(diǎn)。

不妨設(shè)v0是D中的割點(diǎn)，刪去D中所有出度大于2的頂點(diǎn)和入度大于2的頂點(diǎn)之間的弧，得到新的圓有向圖，記作D′。連續(xù)的頂點(diǎn)集v0,v1,…,vn-1,v0在D′中誘導(dǎo)出一個(gè)扁條。因?yàn)閚≥5，由引理6(3)，C1,2(D′)中存在哈密爾頓圈。

情形2：圓有向圖D中有兩個(gè)以上割點(diǎn)。

刪去D中所有出度大于2的頂點(diǎn)個(gè)入度大于2的頂點(diǎn)之間的弧，得到新的圓有向圖，記作D′。此時(shí)的D′是由一系列扁條的并集構(gòu)成。

又因?yàn)関a1+b1-2→va1+b1→va1+b1+2，va1+b1-1→va1+b1→va1+b1+2，va1+b1+1→va1+b1+2，由(1,2)步競(jìng)爭(zhēng)圖的定義，va1+b1-2va1+b1+1,va1+b1-1va1+b1+1分別是C1,2(D′)中的邊。

當(dāng)b1=2時(shí)，va1+1va1va1+b1+1va1+b1是C1,2(D′)中的一條路。

當(dāng)b1>2時(shí)，va1+1va1va1+2va1+3…va1+b1-1va1+b1+1va1+b1是C1,2(D′)中的一條路。

又因?yàn)関a2+b2-2→va2+b2→va2+b2+2，va2+b2-1→va2+b2→va2+b2+2，va2+b2+1→va2+b2+2，由(1,2)步競(jìng)爭(zhēng)圖的定義，va2+b2-2va2+b2+1,va2+b2-1va2+b2+1分別是C1,2(D′)中的一條路。

∪{var+br}。

又因?yàn)関ar+br-2→var+br→var+br+2，var+br-1→var+br→var+br+2，var+br+1→var+br+2，由(1,2)步競(jìng)爭(zhēng)圖的定義，var+br-2var+br+1,var+br-1var+br+1分別是C1,2(D′)中的邊。

當(dāng)br=2時(shí)，var+1varvar+br+1var+br是C1,2(D′)中的一條路。

當(dāng)br>2時(shí)，var+1varvar+2var+3…var+br-1var+br+1var+br是C1,2(D′)中的一條路。

把上述的r條路按照事先安排好順序連起來(lái)就構(gòu)成C1,2(D′)中的一個(gè)哈密爾頓圈，再由推論1，C1,2(D′)中存在哈密爾頓圈。

當(dāng)n階強(qiáng)連通圓有向圖D中下標(biāo)相鄰的頂點(diǎn)同時(shí)是割點(diǎn)時(shí)，C1,2(D′)中是否還有哈密爾頓圈存在。先證明引理7和引理8。

引理7 若n階強(qiáng)連通圓有向圖D中連續(xù)出現(xiàn)3個(gè)以上下標(biāo)相鄰的頂點(diǎn)同時(shí)是割點(diǎn)，則C1,2(D′)中不存在哈密爾頓圈。

引理8 若n階強(qiáng)連通圓有向圖D中出現(xiàn)兩對(duì)以上下標(biāo)相鄰的頂點(diǎn)同時(shí)是割點(diǎn)，則C1,2(D)中不存在哈密爾頓圈。

由引理7和引理8，只需要討論下標(biāo)相鄰的兩個(gè)頂點(diǎn)在圓有向圖D中同時(shí)是割點(diǎn)的情形。

定理5 若n(n≥5)階強(qiáng)連通圓有向圖D下標(biāo)相鄰的頂點(diǎn)同時(shí)是割點(diǎn)且有一個(gè)割點(diǎn)的出度大于2，其余的都不是割點(diǎn)，則C1,2(D)中存在哈密爾頓圈。

在圓有向圖D中，因?yàn)閐+(v0)>2，所以有vn-1→v0→v3,v1→v3,v2→v3，再由(1,2)步競(jìng)爭(zhēng)圖的定義，vn-1v1∈E(C1,2(D)),vn-1v2∈E(C1,2(D))。

當(dāng)n是奇數(shù)時(shí)，哈密爾頓圈vn-1v1v0v3v5v7…vn-2

vn-3vn-5…v4v2vn-1是C1,2(D)的子圖，所以C1,2(D)中存在哈密爾頓圈。

當(dāng)n是偶數(shù)時(shí)，哈密爾頓圈vn-1v1v0v3v5v7…

vn-3vn-2vn-4…v4v2vn-1是C1,2(D)的子圖，所以C1,2(D)中存在哈密爾頓圈。

定理6 若n(n≥5)階強(qiáng)連通圓有向圖D中僅有2個(gè)下標(biāo)相鄰的頂點(diǎn)同時(shí)是割點(diǎn)且有一個(gè)割點(diǎn)的出度大于2，其余下標(biāo)不相鄰的割點(diǎn)出度也大于2，則C1,2(D)中存在哈密爾頓圈。

證明(1) 設(shè)va1-1,va1是n(n≥5)階強(qiáng)連通圓有向圖D中兩個(gè)下標(biāo)不相鄰的割點(diǎn)。存在以下兩種情形：

1) 連續(xù)的頂點(diǎn)集{va1,va1+1,va1+2,…,va1+b1}構(gòu)成的扁條B1是D的子有向圖。因?yàn)閐+(va1)>2，所以b1≥3。由引理6，得：

當(dāng)b1=3時(shí)，C1,2(B1)為K3∪{va1+b1}；

2) 記a1+b1=a2，連續(xù)的頂點(diǎn)集{va2,va2+1,va2+2,…,va2+b2}構(gòu)成的扁條B2也是D的子有向圖。因?yàn)閐+(va2)>2，所以b2≥3。由引理6，得：

當(dāng)b2=3時(shí)，C1,2(B2)為K3∪{va2+b2}；

∪{va2+b2}。

重復(fù)上述過(guò)程，記ar-1+br-1=ar，連續(xù)的頂點(diǎn)集{var,var+1,var+2,…,var+br}構(gòu)成的扁條Br也是D的子有向圖，此時(shí)var+br=var-1。因?yàn)閐+(var)>2，所以b2≥3。由引理6，得：

當(dāng)br=3時(shí)，C1,2(Br)為K3∪{var+br}；

∪{var+br}。

(2) 在圓的有向圖D中，因?yàn)閐+(vai)>3(i=1,2,…,r-1)，所以有以下兩種情形：

1) 當(dāng)bi=3(i=1,2,…,r-1)時(shí)，因?yàn)関ai→vai+bi→vai+bi+3,vai+bi+1→vai+bi+3，vai+bi+2→vai+bi+3。

由(1,2)步競(jìng)爭(zhēng)圖的定義，vaivai+bi+1∈E(C1,2(D))，vaivai+bi+2∈E(C1,2(D))。同理，有vai+1vai+bi+1,vai+1vai+bi+2,vai+2vai+bi+1vai+2vai+bi+2∈E(C1,2(D))。根據(jù)(1)，vai+1vaivai+bi+1vai+bi,vai+2vai+bi+2分別是C1,2(D)中的路。

2) 當(dāng)br≥4(i=1,2,…,r-1)時(shí)，因vai+bi-2→vai+bi→vai+bi+3,vai+bi+1→vai+bi+3，vai+bi+2→vai+bi+3。

由(1,2)步競(jìng)爭(zhēng)圖的定義，vai+bi-2vai+bi+1,vai+bi-2vai+bi+2∈E(C1,2(D))，同理，有vai+bi-1vai+bi+1,vai+bi-1vai+bi+2∈E(C1,2(D))。

根據(jù)(1)，vai+1vaivai+3vai+5…vai+bi-1vai+bi+1vai+bi，vai+2vai+4…vai+bi-2vai+bi+2(bi為偶數(shù))或者vai+2vai+4…

vai+bi-1vai+bi+2(bi為奇數(shù))分別是C1,2(D)中的兩條路。

把上述的2(r-2)條路按照事先拍好的順序連起來(lái)構(gòu)成C1,2(D)中的兩條不相交的路，記作P1,P2，其中P1的起點(diǎn)終點(diǎn)分別為va1+1,var；P2的起點(diǎn)終點(diǎn)分別為va1+2,var+2。

(3) 在圓有向圖D中，存在以下兩種情形：

1) 因?yàn)閐+(va1)>3，所以有va1 -1→va1→va1 +3,va1 +1→va1 +3va1 +2→va1 +3由(1,2)步競(jìng)爭(zhēng)圖的定義，va1-1va1+1∈E(C1,2(D)),va1-2va1+2∈E(C1,2(D))通過(guò)va1-1把(2)中的兩條路P1,P2連接起來(lái)構(gòu)成一條新的路，記為P，其中P的起點(diǎn)終點(diǎn)分別是var,va1+2。

2) 因?yàn)閐+(var)>3，所以br≥3。

當(dāng)br=3時(shí)，因?yàn)镃1,2(Br)為K3∪{var+br}，所以varvar+2∈E(C1,2(D))，則路P起點(diǎn)終點(diǎn)相連，構(gòu)成C1,2(D)中的一個(gè)哈密爾頓圈。

∪{var+br}，所以varvar+3var+5var+7…var+br-3var+br-1var+br-2var+br-4…var+4var+2(br為偶數(shù)) 或者varvar+3var+5var+7…

var+br-2var+br-1var+br-3var+br-5…var+4var+2(br為奇數(shù))是C1,2(D)中的路，與路P的起點(diǎn)終點(diǎn)相連構(gòu)成C1,2(D)中的哈密爾頓圈。

4 結(jié) 論

以上研究了所有的n階(n≥5)的強(qiáng)連通圓有向圖D中(1,2)步競(jìng)爭(zhēng)圖中存在哈密爾頓圈的條件，非強(qiáng)連通的圓有向圖D中(1,2)步競(jìng)爭(zhēng)圖中顯然不存在哈密爾頓圈，因?yàn)镈中存在出度為0的頂點(diǎn)或孤立點(diǎn)，這些點(diǎn)不與任何其他頂點(diǎn)構(gòu)成(1,2)步競(jìng)爭(zhēng)，階n小于5的強(qiáng)連通圓有向圖的(1,2)步競(jìng)爭(zhēng)圖可以通過(guò)畫(huà)圖得到，它的(1,2)步競(jìng)爭(zhēng)圖中也不存在哈密爾頓圈。

[1] UTTONR D， BRIGHAM R. A Characterization of Competition Graphs[J]. Discrete Appl Math, 1983,6(3): 315-317

[2] LUNDGREN J, MAYBEE S. A character ization of Fraphs of Competition Numberm[J]. Discrete Applied Mathematics New York, 1983,6(3), 319-322

[3] KIMH, CHO S, NAM Y. The M-step Competition Graph of a Digraph[J]. Discrete Appl, Math,2000,105: 115-127

[4] MERZ S , LUNDGREN R K, REID B. The Domination and Competition Graphs of a Tournament[J]. Graph Theory,1998,29(2):103-110

[5] FACTOR K, MERZ S. The (1,2)Step Competition Graph of aTournament[J]. Discrete Appl Math,2011,59(2-3): 100-103

[6] BONDY J, MURTY U. Graph Theory With Application[M]. New York: Springer, 2007

[7] BANG-JENSEN J, GUTING. Digraphs: Theory,Algorithms and Applications in: Spring Monographs in Mathematics[M]. London: Spring-Verlag,2001

[8] BANG-JENSEN J,HUANG J.Decomposing Locally Semicomplete Digraphs into Strong Spanning Subdigraphs[J].Journal of ComBina-torial Theory，Series B,2012,102(3): 701-714

[9] BANG-JENSEN J, HUANG J. Arc-Disjoint In-and Out-Branchings With the Same Root in Locally Semicomplete Digraphs[J]. Journal of Graph Theory, 2014,77(4): 278-298

The (1,2) Step Competition Graph of Round Digraph Contains Hamiltonian Cycles

CUIJian1,YEWang2

(1.Basic Medicine Department, Fenyang College, Shanxi Medical University, Shanxi Luliang 032200, China; 2. School of Mathematical Science, Shanxi University, Shanxi Taiyuan 030000, China)

With regard to the (1,2) step competition graph structure of round digraph, this paper puts forward whether the (1,2) step competition graph of round directed graph contains Hamilton cycle, and through special to general method, receives the following conclusion: Hamilton cycle is contained in order of strongly connected directed graph of the (1,2)step competition graph, and the rest of the situation of round digraph (1,2)step competition graphs does not contain Hamilton cycle.

round digraph; (1,2)step competition graph; Hamilton cycle

O157.5

A

2017-04-12；

2017-05-30.

崔建(1988-) ，男，山西呂梁人，碩士，從事圖論和機(jī)器學(xué)習(xí)研究。

責(zé)任編輯：代小紅