禁用兩個(gè)子圖的圖的全控制數(shù)

楊樹承, 胡夫濤, 張昶旭

(安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,合肥 230601)

1 研究背景

本文中的圖G=(V(G),E(G))是頂點(diǎn)集為V(G),邊集為E(G)的無環(huán)且無重邊的簡單無向圖,圖G的任一頂點(diǎn)v,其開鄰域N(v)為在G中和點(diǎn)v相鄰的所有點(diǎn)的集合,閉鄰域記為N[u]=N(u)∪{u}.頂點(diǎn)v的度是指與v相鄰點(diǎn)的數(shù)目,記為d(v)=|N(v)|.如果頂點(diǎn)v的度為0,則稱它為孤立點(diǎn).圖G中點(diǎn)的度的最小值和最大值為圖G的最小度和最大度, 分別用δ(G)和Δ(G)表示.如果圖的頂點(diǎn)數(shù)目|V(G)|=n, 則稱圖G為n階圖.通常用e=uv表示G中的一條邊,其中u和v是e的兩個(gè)端點(diǎn), 稱u和v是鄰接的, 記為u～v.如果圖G的任意兩個(gè)點(diǎn)都有路相連,則稱圖G為連 通圖.設(shè)S?V,稱頂點(diǎn)集為S, 邊集為G中兩個(gè)端點(diǎn)都在S中的圖為由S生成的導(dǎo)出子圖,記為〈U〉.沒有給出定義的基本符號和圖論術(shù)語[1].把n個(gè)頂點(diǎn)順次連接起來形成的圖稱為路, 記為Pn.含有n個(gè)點(diǎn)的完全圖, 記為Kn, 是指任意兩個(gè)頂點(diǎn)都鄰接的簡單圖.如果一個(gè)圖G的頂點(diǎn)集可以被劃分成兩個(gè)子集X,Y, 并且每條邊一端點(diǎn)在X中另一個(gè)端點(diǎn)在Y中, 那么G稱為二部圖, 記作G[X,Y].如果圖G[X,Y]在集合X中的每一個(gè)頂點(diǎn)都和Y中的每一個(gè)頂點(diǎn)鄰接,則稱G為完全二部圖, 設(shè)|X|=s,|Y|=t, 完全二部圖G表示為Ks,t.特別的K1,3稱為爪圖, 見圖1.

圖1 爪圖K1,3.Figure1 Claw graph K1,3

圖2 圖G是E圖,圖H是網(wǎng)圖Figure 2 Graph G was E graph,graph H was net graph

圖3 D圖Figure 3 D graph

設(shè)D是V的子集.若不在D中的每個(gè)點(diǎn)都至少和D中一點(diǎn)相鄰, 則稱D為G的控制集.最小控制集所含的頂點(diǎn)數(shù)稱為圖G的控制數(shù),記為γ(G).根據(jù)實(shí)際需要, 還引申出很多其他變形的控制.如果不含孤立點(diǎn)的圖G的控制集D的導(dǎo)出子圖〈D〉不含孤立點(diǎn), 則稱D為G的全控制集.圖G的最小全控制集含有的頂點(diǎn)數(shù)稱為全控制數(shù), 記為γt(G).Pfaff等[2]證明了求解圖的全控制數(shù)是NP-完備的.

圖的控制數(shù)的研究可以追溯到1850年.圖的控制問題和相關(guān)子集問題的研究是圖論研究中心熱點(diǎn),引起了人們廣泛的研究, 相關(guān)研究成果有幾千篇論文[3-6].在圖的控制論中,圖的全控制是研究比較多的.Henning于2009年撰寫了一篇圖的全控制問題的綜述[7].

對于無爪圖的全控制數(shù)的研究有很多[8-9].對于禁用兩個(gè)子圖的圖的全控制數(shù)研究暫時(shí)還未見到.本文考慮了禁用爪圖和D圖的N≥2階連通圖G全控制數(shù)得到γt(G)≤2「n/4?.

2 主要結(jié)論

設(shè)G=(V,E)是一個(gè)簡單無向圖,u是V中任一點(diǎn)和X是不包含u的頂點(diǎn)子集.記d(u,X)是G[X∪{u}]中最長的以u為端點(diǎn)的路的長度.設(shè)S?V,記

引理2.1 如果P=v1v2…vl是G中的一條最長路,則對任意i∈[l-1],

對于禁用兩個(gè)子圖的圖的成對控制數(shù)研究暫時(shí)還未見到.本文得到了無爪圖和無D圖時(shí)全控制數(shù)的上界.

定理2.1 設(shè)G是n≥2階連通無爪和無D的圖,則γt(G)≤2「n/4?.

證明：首先考慮n≤6的情形.設(shè)u是G中的一個(gè)最大度點(diǎn).當(dāng)Δ(G)≤n-2時(shí),G至多有一個(gè)點(diǎn)v不與u相鄰,此時(shí)這樣的點(diǎn)v一定與u的某個(gè)鄰點(diǎn)w相鄰,則{u,w}是G的一個(gè)全控制集,所以γt(Pn)≤2.當(dāng)Δ(G)=2時(shí),G是階數(shù)為n的路Pn,此時(shí)γt(Pn)≤2「n/4?.剩余的情況為n=6且d(u)=3.設(shè)G不與u相鄰的兩個(gè)點(diǎn)為s,t.若s～t,則{u,w,s,t}是G的一個(gè)全控制集,所以γt(G)≤4.若點(diǎn)s與點(diǎn)t不相鄰,則{u,s′,t′,t}是G的一個(gè)全控制集,其中s′∈N(s)∩N(u),t′∈N(t)∩N(u),所以γt(G)≤4.

下面設(shè)n>6.下證總是存在U?V(G),|U|=m且4≤m≤6,〈U〉是連通的,使得γt(〈U〉)≤「m/2?且〈V-U〉是連通的.此時(shí)根據(jù)歸納法原理γt(G)≤γt(〈U〉)+γt(〈V-U〉)≤2「m/4?+2「n-m/4?≤2「n/4?.

N(v1)?S,

N(v2)?S.

情形1v1～v3.N(w)∩{v1,v2,…,v6}=?且N(v1)∩{v4,v5,v6}=?.

取U={v1,v2,v3,v4,w},〈U〉是連通的,γt(〈U〉)=2且〈V-U〉是連通圖.

情形2v1～v7.N(w)∩{v1,v2,…,v6}=?且N(v1)∩{v3,v4,v5,v6}=?.

取U={v2,v3,v4,w},〈U〉是連通的,γt(〈U〉)=2且〈V-U〉是連通圖.

情形3v2～v4.N(w)∩{v1,v2,…,v6}=?且N(v1)∩{v3,v4,v5,v6,v7}=?.

取U={v1,v2,v4,w},〈U〉是連通的,γt(〈U〉)=2且〈V-U〉是連通圖.

情形4v2～v5.N(w)∩{v1,v2,…,v6}=?,N(v1)∩{v3,v4,v5,v6,v7}=?,N(v2)∩{v4}=?.

由于〈v2,v4,v5,v6〉不是爪圖,一定有v2～v6或v4～v6.分以下2種情形考慮.

1)v2～v6

2)v4～v6

情形5v2～v6.N(w)∩{v1,v2,…,v6}=?,N(v1)∩{v3,v4,v5,v6,v7}=?,N(v2)∩{v4,v5}=?.

情形6v2～v7.N(w)∩{v1,v2,…,v6}=?,N(v1)∩{v3,v4,v5,v6,v7}=?,N(v2)∩{v4,v5,v6}=?.

情形7v3～v6.N(w)∩{v1,v2,…,v6}=?,N(v1)∩{v3,v4,v5,v6,v7}=?,N(v2)∩{v4,v5,v6,v7}=?.

情形8v3～v7.N(w)∩{v1,v2,…,v6}=?,N(v1)∩{v3,v4,v5,v6,v7}=?,N(v2)∩{v4,v5,v6,v7}=?,N(v3)∩{v6}=?.

情形9v4～v6.N(w)∩{v1,v2,…,v6}=?,N(v1)∩{v3,v4,v5,v6,v7}=?,N(v2)∩{v4,v5,v6,v7}=?,N(v3)∩{v6,v7}=?.

情形10v4～v7.N(w)∩{v1,v2,…,v6}=?,N(v1)∩{v3,v4,v5,v6,v7}=?,N(v2)∩{v4,v5,v6,v7}=?,N(v3)∩{v6,v7}=?,N(v4)∩{v6}=?.

由于〈w,v3,v4,v7〉不是爪圖,所以v3～v7.由于v3～v7已經(jīng)在情形8中進(jìn)行了詳細(xì)的討論,這里不再贅述.

情形11v5～v7.N(w)∩{v1,v2,…,v6}=?,N(v1)∩{v3,v4,v5,v6,v7}=?,N(v2)∩{v4,v5,v6,v7}=?,N(v3)∩{v6,v7}=?,N(v4)∩{v6,v7}=?.

3 結(jié) 語

注意到,對于至少含兩個(gè)點(diǎn)的路Pn,γt(Pn)≤2「n/4?.顯然路是不含爪和D的圖,因此定理2.1給出的上界是緊的.

對于n階無爪連通圖G的全控制數(shù)的研究非常多,2000年,Favaron和Henning[10]證明了:若δ(G)≥3, 則γt(G)≤n/2.2007年, Stephan和Anders[11]證明了:δ(G)≥4,則γt(G)≤3n/7.對于有兩個(gè)禁用子圖的全控制數(shù)研究還比較少,本文給出了無爪圖和不含D圖的全控制數(shù)的上界.此后可以考慮禁用其他兩個(gè)子圖的全控制數(shù)的上界問題,比如禁用一些比D圖更大一點(diǎn)的子圖.