張剛，吳寶音都仍

(新疆大學 數(shù)學與系統(tǒng)科學學院，新疆 烏魯木齊 830017)

0 引言

除非特別說明,本文中G=(V,E)均表示一個頂點集為V=V(G),邊集為E=E(G)的有限簡單圖.我們用n=|V|與m=|E|分別表示圖G 的頂點數(shù)與邊數(shù).對任意的u,v ∈V(G),如果uv ∈E(G),那么我們稱u 在圖G中是v 的一個鄰點,反之亦然.對任一v ∈V(G),v 的開鄰域定義為集合NG(v)=N(v)={u ∈V(G)|uv ∈E(G)},v 的閉鄰域定義為集合NG[v]=N[v]=N(v)∪{v}.另外,dG(v)=d(v)=|N(v)| 表示頂點v 在圖G 中的度數(shù).通常,Δ(G)和δ(G)被稱為圖G的最大度和最小度.設S 是G 的一個頂點子集,則S的開鄰域記為NG(S)=N(S)=∪v∈SN(v)S,S的閉鄰域記為NG[S]=N[S]=N(S)∪S.我們用G[S]表示圖G中由S導出的子圖,用G-S 表示圖G 中V S 的導出子圖.對于其他未定義的術語和概念，讀者們可參閱文獻[1].

設F 是一個連通圖集,對任一圖G,如果頂點子集D 使得G-N[D]不包含任一F 中的F 圖作為子圖,那么D 被叫做圖G 的一個F 孤立集,且圖G 中最小的一個F 孤立集D 的階數(shù)被稱為圖G 的F 孤立數(shù),記為ι(G,F).另外,一個頂點子集D 被稱為圖G 的一個控制集,如果V(G)D 中的每個頂點在D 中都至少有一個鄰點.圖G 中最小的一個控制集D 的階數(shù)即是圖G 的控制數(shù),記為γ(G).顯然,ι(G,{K1})=γ(G).

圖的孤立, 亦被稱為部分控制, 它是經典控制理論的一種自然推廣. 2017 年, Caro 和Hansberg[2]首次引入了這些概念. 對于該領域進一步的研究, 可參閱文獻[3-7]. 除此之外, 對于一些經典控制問題, 讀者們可參閱文獻[8-14].

1 主要結果

本文得到的主要結論如下,其詳細的證明將被放在第2 小節(jié)進行.

受此啟發(fā),對任意的正整數(shù)k,我們希望考慮F={Pk}的情形.由此,提出問題:計算n 個頂點的連通圖G 中ι(G,{Pk}) 的準確上界.顯然,因為圖G 的一個Ck∪Tk+1孤立集一定是圖G 的一個{Pk+1} 孤立集,有ι(G,{Pk+1})≤ιtreek(G).

推論4如果G/=C7是一個n 個頂點的連通圖,那么ι(G,{P4})≤n

4,且這個上界是緊的.

定義girth(G)表示圖G 的圍長,即是圖G 中最短的一個導出圈的長度.我們提出下列猜想,其實際上是定理1 的一個推廣.

2 證明

在這一節(jié),我們將會證明本文的主要定理.下面首先給出幾個引理.其中,引理1、引理2、引理3易證,我們將其證明留給讀者.

引理4假設F 是一個連通圖集,G=(V,E)是一個有限簡單圖.對于任意一個頂點子集S,如果G[S]中有一個F 孤立集D,且使得E(SN[D],V S)=?,那么ι(G,F)≤|D|+ι(G-S,F).

證明設D′是G-S 的一個F 孤立集,且|D′|=ι(G-S,F).我們僅需證明D ∪D′是G 的一個F 孤立集即可.反證如下,假設G-N[D ∪D′] 中存在一個F 中的F 圖作為其子圖.根據(jù)D 和D′的選擇,我們有V(F)?(SN[D])∪((V S)N[D′]),V(F)∩(SN[D])/=?和V(F)∩((V S)N[D′])/=?.然而,這是不可能的,因為F 是連通的且E(SN[D],V S)=?.

令V(G)={v1,v2,···,v7},設N(v1)={v2,v3,v4},V(G)N[v1]={v5,v6,v7}.如果|E(G-N[v])|≤2,則取D={v1},于是(G) ≤|D|=1.所以G-N[v1]～=C3.因為G 是連通的,根據(jù)其對稱性,此時我們不妨假設v2v5∈E(G),顯然N(v5)={v2,v6,v7}.注意到如果v3v4/∈E(G),則取D={v5},而此時(G)≤|D|=1.因此我們假設v3v4∈E(G).如果此時dG(v2)=3,那么G-N[v2]/=C3,所以我們可以取D={v2},同時有(G)≤|D|=1.顯然{v1,v5}?N(v2),所以dG(v2)=2.如果{v3,v4,v6,v7}中存在一個頂點x 使得dG(x)=3,那么dG-N[x](v2)=1,所以可取D={x},進而有(G)≤|D|=1.因此,對于每個x ∈{v3,v4,v6,v7},dG(x)=2,那么當前可取D={v2},也有(G)≤|D|=1.

為了方便起見,如果圖G 的一個連通分支同構于C3或者C7,那么我們稱之為壞分支,反之我們稱之為好分支.

如果Hb=?,顯然{v}是G[N[v]]的一個{C3,K1,3,P4}孤立集,根據(jù)引理3 和引理4,我們有

圖1 存在某個x ∈N(v)使得Hxb/=?

子情況1.1(G-X)v/∈{C3,C7}.

根據(jù)歸納假設,再結合引理3 和引理4,我們有

子情況1.2(G-X)v～=C3.

子情況1.3(G-X)v～=C7.

根據(jù)當前的假設,等價的,對于任意一個H ∈Hb,有|N(H)∩N(v)|≥2.下面的證明,我們將分為兩種子情況來討論.

子情況2.1存在一個H ∈Hb,H～=C3.

子情況2.1.1(G-X)v/∈{C3,C7}.

根據(jù)歸納假設,再結合引理3 和引理4,我們有

子情況2.1.2(G-X)v～=C3.

圖2 H′～=C3～=(G-X)v

子情況2.1.3(G-X)v～=C7.

結合當前假設,我們也可得到Δ(G)=dG(v)=3,如圖3 所示.因為|N(H′)∩N(v)|≥2,所以存在x′使得x′∈(N(H′)∩N(v)){x}.注意到{v,x′}是G[Y]的一個{C3,K1,3,P4}孤立集,因此根據(jù)引理3 和引理4,以及歸納假設,我們有

圖3 H′～=C3，但(G-X)v～=C7

子情況2.2任意一個H ∈Hb,H～=C7.

子情況2.2.1存在兩個H1,H2∈Hb使得某個x′∈N(H1)∩N(H2)∩N(v).

圖4 存在一個x′∈N(v)使得x′∈N(H1)∩N(H2)

子情況2.2.2任意兩個H1,H2∈Hb,N(H1)∩N(H2)∩N(v)=?.

因為對于每個H ∈Hb,|N(H)∩N(v)|≥2,所以當前的條件暗示著Δ ≥2b.再結合Δ-2 ≤b,我們有Δ ≤4和b ≤2.因此,Δ ∈{3,4},b ∈{1,2}.于是,現(xiàn)在我們僅需再考慮Δ 和b 兩兩組合可能出現(xiàn)的四種子情況即可.然而,當Δ=3 且b=2 時,如圖5 所示,我們已在子情況2.2.1 進行了討論.當Δ=4 且b=1 時,如圖6 所示,該子情況已經與Δ-2 ≤b 矛盾.

圖5 Δ=3 且b=2

圖6 Δ=4 且b=1

最后我們來討論Δ=3 且b=1和Δ=4 且b=2 兩種子情況.如果Δ=3 且b=1,如圖7 所示,那么我們假設Hb={H′},xy,x′y′∈E(G),其中x,x′∈N(v),y,y′∈V(H′),且x/=x′,y/=y′.令X={x,x′}∪V(H′).因為dG-X(v)=dG(v)-2=Δ-2=3-2=1,所以G-X 中一定沒有壞分支.顯然,此時{y,y′} 是G[X]的一個{C3,K1,3,P4}孤立集.根據(jù)歸納假設,再結合引理3 和引理4,我們有

圖7 Δ=3 且b=1

圖8 Δ=4 且b=2

到此完成定理1 的證明.