崔 建，葉 旺

(1.山西醫(yī)科大學汾陽學院 基礎醫(yī)學部，山西 呂梁 032200; 2.山西大學 數學科學學院，太原 030000)

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

崔 建1，葉 旺2

(1.山西醫(yī)科大學汾陽學院 基礎醫(yī)學部，山西 呂梁 032200; 2.山西大學 數學科學學院，太原 030000)

針對圓有向圖的(1,2)步競爭圖的結構，提出了競爭圖中是否存在哈密爾頓圈；通過特殊到一般的方法得到如下結論：對于階數n(n≥5)的強連通圓有向圖的(1,2)步競爭圖中存在哈密爾頓圈，而其余情形的圓有向圖的(1,2)步競爭圖中則不存在哈密爾頓圈。

圓有向圖；(1,2)步競爭圖；哈密爾頓圈

0 引 言

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

如果xy∈A(D)或者yx∈A(D)，那么x和y是相鄰。如果n個頂點的有向圖D的頂點可標號為v0,v1，…，vn-1使得對每個i，總有N+(vi)={vi+1,vi+2,…，vi+d+(vi)}和N-(vi)={vi-d-(vi),vi-(vi)+1,…，vi-1}(所有下標均取模n，以后不再重復說明)，稱D是圓有向圖，稱序是v0,v1，…，vn-1。

有向圖D=(V,A)，對于每個X?V且X≤k-1，如果D-X是強連通的，則D是k強連通的，簡稱D是k強的。如果D是k(k≥2)強的，那么D也是k-1強的。

設D是一個圓有向圖，v0,v1,…,vn-1是圓有向圖D的一個圓坐標，連續(xù)的頂點集{va,va+1,…，va+b}(其中a∈{0,1…,n-1},b>1)在D中構成一個扁條，記住B，如果這些頂點滿足式(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)

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

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

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

設D=(V,A)是一個有向圈，D=(V,E)是一個無向圈。如果無向圖G=(V,E)滿足,V(G)=V(D)并且xy∈E(G)，當且僅當D中存在頂點z≠x,y使得dD-y(x,z)=1,dD-x(y,z)=1,那么稱G為D的競爭圖，記為C(D)。

設T是l個頂點的競賽圖，稱D=T(S1,S2,…,Sl)是T的擴充競賽圖，C1,2(T)是T的(1,2)步競爭圖，并稱H=C1,2(T)[S1,S2,…,Sl]是D的同等擴充。

圖2 a=0,b=5的扁條B以及它的競爭圖C(B)和(1，2)步競爭圖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)

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

1 準備知識

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

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

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

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

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

引理4D是一個有向圖，C(D)是D的競爭圖，C1,2(D)是D的(1,2)步競爭圖，則C(D)?C1,2(D)。

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

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

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

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

證明不妨設v0是階為n的1強連通圓有向圖D的割點，由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)構成的完全圖是C(D)的子圖。

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

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

根據上面的證明，猜想下面的結論是正確的。

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

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

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

當D是一個n階的1強的圓有向圖時，考慮C1,2(D)中是否存在哈密爾頓圈。若C1,2(D)中存在哈密爾頓圈，D應該滿足什么樣的條件。

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

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

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

證明情形1：圓有向圖D中只有一個割點。

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

情形2：圓有向圖D中有兩個以上割點。

刪去D中所有出度大于2的頂點個入度大于2的頂點之間的弧，得到新的圓有向圖，記作D′。此時的D′是由一系列扁條的并集構成。

又因為va1+b1-2→va1+b1→va1+b1+2，va1+b1-1→va1+b1→va1+b1+2，va1+b1+1→va1+b1+2，由(1,2)步競爭圖的定義，va1+b1-2va1+b1+1,va1+b1-1va1+b1+1分別是C1,2(D′)中的邊。

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

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

又因為va2+b2-2→va2+b2→va2+b2+2，va2+b2-1→va2+b2→va2+b2+2，va2+b2+1→va2+b2+2，由(1,2)步競爭圖的定義，va2+b2-2va2+b2+1,va2+b2-1va2+b2+1分別是C1,2(D′)中的一條路。

∪{var+br}。

又因為var+br-2→var+br→var+br+2，var+br-1→var+br→var+br+2，var+br+1→var+br+2，由(1,2)步競爭圖的定義，var+br-2var+br+1,var+br-1var+br+1分別是C1,2(D′)中的邊。

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

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

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

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

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

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

由引理7和引理8，只需要討論下標相鄰的兩個頂點在圓有向圖D中同時是割點的情形。

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

在圓有向圖D中，因為d+(v0)>2，所以有vn-1→v0→v3,v1→v3,v2→v3，再由(1,2)步競爭圖的定義，vn-1v1∈E(C1,2(D)),vn-1v2∈E(C1,2(D))。

當n是奇數時，哈密爾頓圈vn-1v1v0v3v5v7…vn-2

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

當n是偶數時，哈密爾頓圈vn-1v1v0v3v5v7…

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

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

證明(1) 設va1-1,va1是n(n≥5)階強連通圓有向圖D中兩個下標不相鄰的割點。存在以下兩種情形：

1) 連續(xù)的頂點集{va1,va1+1,va1+2,…,va1+b1}構成的扁條B1是D的子有向圖。因為d+(va1)>2，所以b1≥3。由引理6，得：

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

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

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

∪{va2+b2}。

重復上述過程，記ar-1+br-1=ar，連續(xù)的頂點集{var,var+1,var+2,…,var+br}構成的扁條Br也是D的子有向圖，此時var+br=var-1。因為d+(var)>2，所以b2≥3。由引理6，得：

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

∪{var+br}。

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

1) 當bi=3(i=1,2,…,r-1)時，因為vai→vai+bi→vai+bi+3,vai+bi+1→vai+bi+3，vai+bi+2→vai+bi+3。

由(1,2)步競爭圖的定義，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))。根據(1)，vai+1vaivai+bi+1vai+bi,vai+2vai+bi+2分別是C1,2(D)中的路。

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

由(1,2)步競爭圖的定義，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))。

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

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

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

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

1) 因為d+(va1)>3，所以有va1 -1→va1→va1 +3,va1 +1→va1 +3va1 +2→va1 +3由(1,2)步競爭圖的定義，va1-1va1+1∈E(C1,2(D)),va1-2va1+2∈E(C1,2(D))通過va1-1把(2)中的兩條路P1,P2連接起來構成一條新的路，記為P，其中P的起點終點分別是var,va1+2。

2) 因為d+(var)>3，所以br≥3。

當br=3時，因為C1,2(Br)為K3∪{var+br}，所以varvar+2∈E(C1,2(D))，則路P起點終點相連，構成C1,2(D)中的一個哈密爾頓圈。

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

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

4 結 論

以上研究了所有的n階(n≥5)的強連通圓有向圖D中(1,2)步競爭圖中存在哈密爾頓圈的條件，非強連通的圓有向圖D中(1,2)步競爭圖中顯然不存在哈密爾頓圈，因為D中存在出度為0的頂點或孤立點，這些點不與任何其他頂點構成(1,2)步競爭，階n小于5的強連通圓有向圖的(1,2)步競爭圖可以通過畫圖得到，它的(1,2)步競爭圖中也不存在哈密爾頓圈。

[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-) ，男，山西呂梁人，碩士，從事圖論和機器學習研究。

責任編輯：代小紅