圖的圈和樹(shù)孤立?

張剛，吳寶音都仍

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

0 引言

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

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

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

1 主要結(jié)果

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

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

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

4,且這個(gè)上界是緊的.

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

2 證明

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

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

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

令V(G)={v1,v2,···,v7},設(shè)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.因?yàn)镚 是連通的,根據(jù)其對(duì)稱性,此時(shí)我們不妨假設(shè)v2v5∈E(G),顯然N(v5)={v2,v6,v7}.注意到如果v3v4/∈E(G),則取D={v5},而此時(shí)(G)≤|D|=1.因此我們假設(shè)v3v4∈E(G).如果此時(shí)dG(v2)=3,那么G-N[v2]/=C3,所以我們可以取D={v2},同時(shí)有(G)≤|D|=1.顯然{v1,v5}?N(v2),所以dG(v2)=2.如果{v3,v4,v6,v7}中存在一個(gè)頂點(diǎn)x 使得dG(x)=3,那么dG-N[x](v2)=1,所以可取D={x},進(jìn)而有(G)≤|D|=1.因此,對(duì)于每個(gè)x ∈{v3,v4,v6,v7},dG(x)=2,那么當(dāng)前可取D={v2},也有(G)≤|D|=1.

為了方便起見(jiàn),如果圖G 的一個(gè)連通分支同構(gòu)于C3或者C7,那么我們稱之為壞分支,反之我們稱之為好分支.

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

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

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

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

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

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

根據(jù)當(dāng)前的假設(shè),等價(jià)的,對(duì)于任意一個(gè)H ∈Hb,有|N(H)∩N(v)|≥2.下面的證明,我們將分為兩種子情況來(lái)討論.

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 Δ=3 且b=2

圖6 Δ=4 且b=1

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

圖7 Δ=3 且b=1

圖8 Δ=4 且b=2

到此完成定理1 的證明.