李瑞娟,張新鴻,李勝家

(1.山西大學(xué)數(shù)學(xué)與應(yīng)用數(shù)學(xué)研究所,山西太原 030006;2.太原科技大學(xué)應(yīng)用數(shù)學(xué)系,山西太原 030024)

＊蘊含強(p,q)哈密爾頓性的幾個條件

李瑞娟1,張新鴻2,李勝家1

(1.山西大學(xué)數(shù)學(xué)與應(yīng)用數(shù)學(xué)研究所,山西太原 030006;2.太原科技大學(xué)應(yīng)用數(shù)學(xué)系,山西太原 030024)

利用路收縮技術(shù),證明了,如果有向圖D滿足下列條件中的任何一個,

(1)最小半度δ0(D)≥(n+p+q)/2;

(2)D是(p+q+1)強連通有向圖,且d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,這里,x,y是任意控制頂點對,u,v是任意被控制頂點對;

(3)D的弧數(shù)超過(n-1)2+q2+p;那么D是強(p,q)哈密爾頓的.

路收縮;最小半度;度和;最少弧數(shù);強(p,q)哈密爾頓

O157.5

A

本文僅考慮無環(huán)、無重邊的有向圖.設(shè)D是一個有向圖,我們用n表示D的頂點的個數(shù),用V(D)和A(D)分別表示D的頂點集和弧集.

設(shè)x,y是D上的兩個頂點,如果xy是D的一條弧,那么我們稱x控制y或者y被x控制,記作x→y.所有被x控制的頂點構(gòu)成的集合稱為x的外鄰,記作N+D(x),所有控制x的頂點構(gòu)成的集合稱為x的內(nèi)鄰,記作N-D(x).記d+D(x)=|N+D(x)|,d-D(x)=|N-D(x)|,分別稱為x的外度和內(nèi)度.我們稱x的外度或內(nèi)度為它的半度.如果D是上下文所已知的,則我們忽略上述符號的下標(biāo).

有向圖D的最小外度和最小內(nèi)度分別是指δ+(D)=m in{d+D(x)|x∈V(D)},δ-(D)=m in{d-D(x)|x∈V(D)},最小半度是指δ0(D)=min{δ+(D),δ+(D)}.

對于D上的兩個不同頂點x和y,如果存在頂點z,使得z→x且z→y,則稱x,y是被控制頂點對.如果存在頂點w,使得x→w且y→w,則稱x,y是控制頂點對.

本文中的路和圈是指有向路和有向圈.有向圖D上的哈密爾頓路和圈是指包含所有頂點的路和圈.如果D包含一個哈密爾頓圈,則稱D是哈密爾頓的.設(shè)P是D上的一條路,a,b是P上的兩個頂點,不妨設(shè)在P上a在b之前,P[a,b]表示從a到b的子路.

如果對每一對頂點x和y,在D上總存在一條從x到y(tǒng)的路和一條從y到x的路,則稱D是強連通的,或者稱D是一個強連通有向圖.如果在D上既存在從x到y(tǒng)的哈密爾頓路又存在從y到x的哈密爾頓路,則稱D是強哈密爾頓連通的,或者說,D是強哈密爾頓連通有向圖.如果|V(D)|≥k+1且對任何一個至多k-1個頂點的集合U,都有D-U是強連通的,則稱D是k強連通的或者D是一個k強連通有向圖.

定義1[1]設(shè)D=(V,A)是一個有向圖,設(shè)S是以V(D)為頂點集的完全有向圖中兩兩不相交的路的集合且S中所有路的總長度為q.如果對于所有滿足上述條件的集合S,有向圖D′=(V,A∪S)都有包含S的哈密爾頓圈,則稱D是強q弧哈密爾頓的.如果對所有整數(shù)r(0≤r≤p)刪除D的任意r個頂點得到的有向圖是強q弧哈密爾頓,則稱有向圖D是強(p,q)哈密爾頓的.

顯然,強(0,1)哈密爾頓有向圖恰好是強哈密爾頓連通的.更多結(jié)果參看文獻(xiàn)[6-8].

定義2[2]設(shè)x和y是有向圖D上的兩個不同頂點,P是以V(D)為頂點集的完全有向圖上的一條(x,

(3)一條兩個端點均在V(D)V(P)上的弧屬于H當(dāng)且僅當(dāng)它屬于D.

記H=D/P.如果P是一條弧e,簡單地記H=D/e.設(shè)

S={Pi|Pi是以V(D)為頂點集的完全圖中的一條路,i=1,2,…,s,且這些Pi兩兩不相交}.如果H′=(…((D/P1)/P2)/…)Ps,則稱H′是由D通過收縮S得到的有向圖,記H′=D/S,不難看出,這里的收縮運算并不依賴于路收縮的順序.

本文未給出的術(shù)語和符號可參考文獻(xiàn)[1].下面是本文將用到的一些定理.

定理1[3]如果D是最小半度δ0(D)≥n/2,那么D是哈密爾頓的.

定理2[4]如果D是強連通有向圖且對于D的任意控制頂點對x和y,以及D的任意被控制頂點u和v,有d+(x)+d+(y)+d-(u)+d-(v)≥2n-1,那么D是哈密爾頓的.

定理3[5]如果D的弧數(shù)超過(n-1)2,那么D是哈密爾頓的.

定理4 設(shè)p和q是兩個非負(fù)整數(shù)且滿足1≤p+q≤n-2.如果D的最小半度δ0(D)≥(n+p+q)/2,那么D是強(p,q)哈密爾頓的.

證明 設(shè)r是滿足0≤r≤p的整數(shù),D′是由D刪除任意r個頂點的有向圖.顯然D′包含n-r個頂點.為了證明D是強(p,q)哈密爾頓的,只需證明D′是強q弧哈密爾頓的.設(shè)S是頂點集為V(D′)的完全圖中互不相交的路的集合,且滿足這些路的總長度為q.在有向圖D′上通過收縮S構(gòu)造新的有向圖D″.由于在D′上每收縮一條弧,D′減少一個頂點,故D″包含D-r-q個頂點.進(jìn)而y)路.稱有向圖H是由D通過收縮P到一個新頂點w得到的有向圖,如果滿足下列條件:

(1)V(H)=(V(D)V(P))∪{w};

根據(jù)定理1,D″是哈密爾頓的,從而D′是強q弧哈密爾頓的.結(jié)論得證.

引理設(shè)q≥1是整數(shù)且D是(q+1)強連通有向圖,S是以V(D)為頂點集的完全圖中兩兩不相交的路的集合且S中所有路的總長度為q.如果D′是由D通過收縮S得到的有向圖,那D′是強連通的.

證明 設(shè)S包含的弧分別是e1,e2,…,eq,則(…((D/e1)/e2)/…)/eq=D/S=D′.顯然,只需證明D/e1是q強連通的.令e1=ab,D收縮e1得到新頂點w.設(shè)x,y是D/e1中任意兩個不同頂點.如果x和y都不是新頂點w,由M enger定理,在D上存在q+1條內(nèi)部不相交的(x,y)路.如果這q+1條路中有q條路均不包含a,b,則D/e1有q條內(nèi)部不相交的(x,y)的路.故假設(shè)這q+1條路中存在兩條路P1和P2,使得a∈V(P1),b∈V(P2).注意到,P1[x,w]P2[w+,y]是D/e1上從x到y(tǒng)的路且與其余的q-1條路內(nèi)部不相交,則在此情形下,D/e1上仍有q條內(nèi)部不相交的路.因此,假設(shè)x或y是頂點w.不失一般性,假設(shè)x=w,由M enger定理,在D上有q+1條內(nèi)部不相交的(b,y)路.顯然,這些路中至多有一條包含頂點a.從而,其余q條(b,y)路仍是D/e1上的q條(w,y)路.再由M enger定理以及x,y選取的任意性,D/e1是q強連通有向圖.結(jié)論得證.

定理5 設(shè)p和q是兩個非負(fù)整數(shù)且滿足1≤p+q≤n-2,D是(p+q+1)強連通有向圖.如果對任意控制頂點對x,y以及被控制頂點對u,v.都有d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,那么D是強(p,q)哈密爾頓的.

證明 設(shè)r,D′,S,D″如定理4所定義.顯然D′是(q+1)強連通的,從而由引理,D″是強連通有向圖.又顯然,D″包含n-r-q個頂點.

類似于定理4的證明,只需證明D″是哈密爾頓的.設(shè)S′?V(D″)是收縮后得到的新頂點的集合.任取D″上的控制頂點對x,y以及被控制頂點對u,v.如果x(或y)是S′中的點,那么x(或y)在D″-S′上的外鄰集與S中某條路的終點在D-S上的外鄰集相同.仍用x(或y)表示這條路的終點.類似地,如果u(或v)是S′中的點,那么u(或v)在D″-S′上的內(nèi)鄰集與S中某條路的起點在D-S上的內(nèi)鄰集相同.同樣地,仍用u(或v)表示這條路的起點.注意到,x和y(u和v)仍是D上的控制(被控制)頂點對,故有:

由定理2,D″是哈密爾頓的,結(jié)論得證.

定理6 設(shè)p和q是兩個非負(fù)整數(shù)且滿足1≤q2+p≤n-1.如果D的弧數(shù)超過(n-1)2+q2+p,那么D是強(p,q)哈密爾頓的.

證明 設(shè)r,D′,S,D″如定理4所定義.顯然D′有n-r個頂點,D″有n-r-q個頂點,并且當(dāng)刪除D的r個頂點時,D至多減少了2r(n-r)+r(r-1)條弧.假設(shè)P是S中的一條路.如果在D′中收縮路P,那么D′至多減少了2|A(P)|(n-r-1)條弧.故當(dāng)收縮S中所有的路時.D′至多減少了2q(n-r-1)條弧.因此

由定理3.D″是哈密爾頓的.從而,D是強(p,q)哈密爾頓的.

推論1 如果D的最小半度δ0(D)≥(n+1)/2,那么D是強哈密爾頓連通的.

推論2 設(shè)D是2強連通有向圖.如果對任意控制頂點對x,y以及被控制頂點對u,v,都有d+(x)+d+(y)+d-(u)+d-(v)≥2n+1,那么D是強哈密爾頓連通的.

推論3 如果D的弧數(shù)超過(n-1)2+1,那么D是強哈密爾頓連通的.

[1] Bermond J C,Thomassen C.Cycles in Digraphs-A Survey[J].J Graph Theory,1981,5:1-43.

[2] Ban-jensen J,Gutin G.Digraphs:Theory,A lgorithm s and Applications[M].London:Sp ringer-verlag,2000.

[3] Ghouila-houri A.Une Condition Sufficante D’existence D’un Circuit Hamiltonian[J].C R Acad Sci Paris,1960,25:495-497.

[4] Zhao L C,Meng J H.A Sufficient Condition fo r Hamiltonian Cycles in Digraphs[J].Australas J Combin,1991,32:335-338.

[5] Lew in M.On Maximal Circuits in Directed Graphs[J].J Combin Theory Ser B,1975,18:175-179.

[6] Benvenuti D K,Punnen A P.SC-Hamiltonicity and Its Linkages with Strong Hamiltonicity of A Graph[J].SIAM J D iscrete Math,2010,23:2035-2041.

[7] Hsieh S Y,Kuo C N.Hamiltonian-connectivity and Strongly Hamiltonian-laceability of Folded Hypercubes[J].SIAM J Discrete Math,2007,53:1040-1044.

[8] Meierling D.Local Tournaments with the Minimum Number of Hamiltonian Cycles or Cycles of Length Three[J].D iscrete Math,2010,310:1940-1948.

Some Sufficient Conditions for Strongly(p,q)-Hamilton icity

LI Rui-juan1,ZHANG Xin-hong2,LI Sheng-jia1
(1.Institute of Mathematics and A pp lied Mathematics,Shanxi University,Taiyuan030006,China;
2.Department of Applied Mathematics,Taiyuan University of Science and Technology,Taiyuan030024,China)

U sing the path-contraction technique,w e p rove that if a digraphDsatisfies

(i)the minimum semi-degreeδ0(D)≥(n+p+q)/2(1≤p+q≤n-2),or

(ii)Dis(p+q+1)-strong andd+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1 fo r every pairx,yof dominating vertices and every pairu,vof dominated vertices,or

(iii)Dcontains more than(n-1)2+q2+p;(1≤q2+p≤n-1)arcs,thenDis strongly(p,q)-Hamiltonian.

path-contraction;minim um semi-degree;degree sum;minimum arcs;strongly(p,q)-Hamiltonian

0253-2395(2011)01-0026-03＊

2010-05-24;

2010-06-28

山西省自然科學(xué)基金(2007011002);國家自然科學(xué)基金數(shù)學(xué)天元基金(11026162)

李瑞娟(1980-),女,山西侯馬人,博士,講師.E-mail:ruijuanli@sxu.edu.cn