具有禁止子圖的有向圖是超歐拉有向圖的條件

鄭煥，董暢暢

(新疆師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，新疆 烏魯木齊 830017)

0 引 言

Boesch,Suffel和Tindell[2]在1977年提出了超歐拉問題,他們致力于刻畫出包含生成歐拉子圖的無向圖,同時,他們表示這個問題是非常困難的.Pulleyblank[3]在1979年證明了判定一個無向圖(甚至包含平面無向圖)是否是超歐拉的是NP-完全的.截至今日,已經(jīng)有大量關(guān)于超歐拉無向圖的研究,例如Catlin的研究[4]和他的更新版[5].

禁止誘導(dǎo)子有向圖一直是被廣泛研究的話題.給定一個有向圖K和一個有向圖D,如果對于D的任意一個子圖H,若滿足H≌K,則|A(D〈V(H)〉)|>|A(H)|+1,則稱D不含K子圖.一直在被深入研究的是成為哈密頓的充分條件是不含K1,3子圖,可以參考[10].

1 主要結(jié)論

如果D是非哈密爾頓的,但是強(qiáng)連通的,則在D中存在至少一個S-路或S-圈.A.Kemnitz和 B.Greger給出了定理1中的結(jié)論.

定理1[10]如果R是一個至少有3個點的定向圖且不含圖1中的誘導(dǎo)子圖,則稱R是哈密爾頓有向圖.

圖1 禁止誘導(dǎo)子圖注：圖1中未標(biāo)方向的弧可以看作是任意方向

在定理1中,A.Kemnitz和 B.Greger證明了含有禁止誘導(dǎo)子圖的定向圖是哈密爾頓的其中一種情況,有這個結(jié)論我們可以得到推論1.

推論1設(shè)R是一個至少有3個點的定向圖,如果R不含圖2中的誘導(dǎo)子圖,則稱R是哈密爾頓有向圖.

圖2 禁止誘導(dǎo)子圖注：圖2中未標(biāo)方向的弧可以看作是任意方向

證：假設(shè)R滿足推論中的條件,但是非哈密爾頓有向圖.

令S=(v1,v2,…,vn,v1)是有向圖R中長度最大的有向圈.因為R強(qiáng)連通但非哈密爾頓有向圖,所以在有向圖R中存在一個S-路或S-圈.

情形1. 如果R中沒有S-路,則一定存在一個S-圈C.令vk是S和C公共點,ur在C中是vk的上升點(見圖3).因為在R中沒有S-路,故點vk-1和點vk+1都是與ur不相鄰的點.因而,R({vk-1,vk,vk+1,vr})是R的誘導(dǎo)子圖也是圖2中的第一種或第二種類型.

圖3 沒有S-路存在

圖4 存在S-路

情況2.如果R中有一個S-路P,設(shè)P=(vk,u,u1,…,ur,vk+r)，其中k+r對模n同余;P,vk,以及vk+r使得r是所有S-路中的最小值.

由S是R中長度最大的一個有向圈,得到{(vk+r-1,u),(vk+r-1,ur)}∩A(R)=?.如果(vk+r-1,u)∈A(R),那么S-(vk+r-1,vk+r)+{(vk+r-1,u),(u,u1),…,(ur,uk+r)}就與S是R中長度最大的有向圈的條件相違背;如果(vk+r-1,ur)∈A(R),那么S-(vk+r-1,vk+r)+{(vk+r-1,ur),(ur,vk+r)}同樣與S是R中長度最大的有向圈的條件相違背.因此我們可以得到{(vk+r-1,u),(vk+r-1,ur)}∩A(R)=?且r>1(見圖4).

因為r是所有S-路中的最小值,所以(ur,vk+r-1)?A(R).這就意味著R({vk+r-1,vk+r,vk+r+1,ur})是R的誘導(dǎo)子圖也是圖2中的一種存在情況.

我們受到不含圖1和圖2中禁止誘導(dǎo)子圖的定向圖是哈密爾頓的性質(zhì)啟發(fā),進(jìn)而考慮了在超歐拉有向圖中,是否能找到不能含有哪些禁止誘導(dǎo)子圖能夠使得有向圖滿足超歐拉的性質(zhì)的情形.首先如果有向圖D是強(qiáng)連通的,則在D中一定存在S-路.

定理2設(shè)D是一個至少有3個點的強(qiáng)連通有向圖,如果D不含圖3中的誘導(dǎo)子圖,則稱D是超歐拉有向圖.

圖5 0≤虛線的條數(shù)≤1;0≤實線的條數(shù)≤2

圖6 存在S-路

其中未標(biāo)方向的弧，其方向可任意

證: 設(shè)D是一個至少有3個點的強(qiáng)連通有向圖,且不含圖5中的誘導(dǎo)子圖,但D是非超歐拉有向圖.

令S=(v1,v2,…,vn,v1)是有向圖D中點數(shù)最多的一個歐拉子有向圖且弧數(shù)最多.因為D是強(qiáng)連通有向圖但非超歐拉有向圖,故D中存在一個S-路P;設(shè)P=(vk,u,u1,…,ur,uk+r),其中k+r對模n同余;P,vk以及vk+r使得r是所有S-路中的最小值.

由S是D中點數(shù)最多的歐拉子有向圖,我們可以得到{(u,vk+1),(ur,vk+1)}∩A(D)=?,{(vk+r-1,u),(vk+r-1,ur)}∩A(D)=?.

如果(u,vk+1)∈A(D),那么S-(vk,vk+1)+{(vk,u),(u,vk+1)}就違背了S是D中點數(shù)最多的歐拉子有向圖這一條件;如果(ur,vk+1)∈A(D),那么S-(vk,vk+1)+{(vk,u),(u,u1),…,(ur,vk+1)}同樣也是違背了S是D中點數(shù)最多的歐拉子有向圖這一條件.

綜上所述,{(u,vk+1),(ur,vk+1)}∩A(D)=?且r>1(見圖6).另外,0≤|{(vk-1,u)(u,vk-1)}∩A(D)|≤1;如果{(vk-1,u),(u,vk-1)}?A(D),那么S+{(vk-1,u),(u,vk-1)}就違背了S是D中點數(shù)最多的歐拉子有向圖這一條件.又因為r是所有S-路中的最小值,所以(vk+1,u)?A(D).這就意味著D〈{vk-1,vk,vk+1,u}〉是D的誘導(dǎo)子圖也是圖3中的一種存在情況.

如果(vk+r-1,u)∈A(D),那么S-(vk+r-1,vk+r)+{(vk+r-1,u),(u,u1)，…,(ur,vk+r)}就與S是D中點數(shù)最多的歐拉子有向圖的條件相違背;如果(vk+r-1,ur)∈A(D),那么S-(vk+r-1,vk+r)+{(vk+r-1,ur),(ur,vk+r)}同樣與S是D中點數(shù)最多的歐拉子有向圖的條件相違背.因此我們可以得到{(vk+r-1,u),(vk+r-1,ur)}∩A(D)=?.另外,0≤|{(vk+r+1,ur),(ur,vk+r+1)}∩A(D)|≤1;如果{(vk+r+1,ur),(ur,vk+r+1)}?A(D),那么S+{(vk+r+1,ur),(ur,vk+r+1)}就違背了S是D中點數(shù)最多的歐拉子有向圖這一條件.又因為r是所有S-路中的最小值,所以(ur,vk+r-1)?A(D).這就意味著D({vk+r-1,vk+r,vk+r+1,ur})是D的誘導(dǎo)子圖也是圖5中的一種存在情況.

[1]Bang-Jensen.J,Gutin G. Digraphs: Theory[M].Algorithms and Applications, SecondEdition, Springer, 2010.

[2]Boesch F T,Suffel C,Tindell R.The spanning subgraphs of eulerian graphs[J].Journal of Graph Theory, 1977(1):79-84.

[3]Pulleyblank W R.A note on graphs spanned by Eulerian graphs[J].Journal of GraphTheory, 1979(3):309-310.

[4]Catlin P A.Supereulerian graphs: a survey[J].Journal of Graph Theory,1992(16):177-196.

[5]Lai H J,Shao Y,Yan H.An update on supereulerian Graphs[J].World Scientificand Engineering Academy and Society Transactions on Mathematics, 2013,12(9):926-940.

[6]Alsatami K A,Zhang X D,Liu J,Lai H J.On a class of supereulerian digraphs[J].Applied Mathematics,2016(7):320-326.

[7]Bang-Jensen J,Maddaloni A.Sufficient conditions for a digraph to be supereulerian[J].Journal of Graph Theory,2015,79(1):8-20.

[8]Hong Y, Lai H G,Liu Q.Supereulerian digraphs[J].Discrete Mathematics, 2014,330:87-95.

[9]Faudree R,Flandrin E,Ryjacek Z.Claw-free graphs — A survey[J].Discrete Math.,1997,164:87-147.

[10]Kemnitz A,Greger B.A forbidden subdigraph condition implying an oriented graph to be hamiltonian[J].CiteSeer, 1970.