特殊框架下分?jǐn)?shù)(f,n',m)-臨界消去圖的聯(lián)結(jié)數(shù)條件*

夏幼明, 張?jiān)聘? 高煒

(云南師范大學(xué) 信息學(xué)院,云南 昆明 650500)

1 引 言

在計(jì)算機(jī)網(wǎng)絡(luò)中,若將站點(diǎn)看成頂點(diǎn),站點(diǎn)之間的通道看成頂點(diǎn)之間的邊.那么網(wǎng)絡(luò)中的信息傳遞問題就可以用圖論中的分?jǐn)?shù)因子存在性和因子分解模型來解決.本文忽略站點(diǎn)之間信息傳遞的方向,所考慮的圖均為無向有限簡單圖.設(shè)圖G對(duì)應(yīng)某個(gè)特定結(jié)構(gòu)的網(wǎng)絡(luò),其頂點(diǎn)集和邊集分別為V(G)和E(G).對(duì)任意頂點(diǎn)x∈V(G),記dG(x)和NG(x)分別為x在G中的度和鄰域.δ(G)為G的最小度.對(duì)任意S?V(G),標(biāo)記G[S]表示S的導(dǎo)出子圖.本文中的其他標(biāo)記若無特別說明則與文獻(xiàn)[1]一致.

圖G的聯(lián)結(jié)數(shù)bind(G)用來衡量圖G對(duì)應(yīng)網(wǎng)絡(luò)的易受攻擊性和穩(wěn)定性,其定義為:

由定義可知,分?jǐn)?shù)(f,n')-臨界圖和分?jǐn)?shù)(f,m)-消去圖分別反映的是網(wǎng)絡(luò)中部分站點(diǎn)損壞或部分站點(diǎn)之間的連接損壞的情況下,是否還可以進(jìn)行站點(diǎn)之間的信息傳輸.而分?jǐn)?shù)(f,n',m)-臨界消去圖反映的是部分站點(diǎn)和連接同時(shí)被損壞的情況下,網(wǎng)絡(luò)信息傳輸?shù)目尚行?而圖的聯(lián)結(jié)數(shù)恰恰是反應(yīng)網(wǎng)絡(luò)易受攻擊性的一個(gè)參數(shù),因此從數(shù)學(xué)上研究它們之間的相互關(guān)系對(duì)于網(wǎng)絡(luò)保護(hù)和信息流傳輸都有重要意義.

文獻(xiàn)[2]研究了聯(lián)結(jié)數(shù)與分?jǐn)?shù)(f,n',m)-臨界消去圖的相互關(guān)系,得到如下結(jié)果:

和

則G是分?jǐn)?shù)(f,n',m)-臨界消去圖.

這兩個(gè)結(jié)果在一定程度上擴(kuò)展了文獻(xiàn)[3-4]中的相關(guān)結(jié)論.其他關(guān)于分?jǐn)?shù)臨界圖和分?jǐn)?shù)消去圖的結(jié)果可參考文獻(xiàn)[5-9].在已有結(jié)論的基礎(chǔ)上,本文繼續(xù)研究聯(lián)結(jié)數(shù)與分?jǐn)?shù)(f,n',m)-臨界消去圖的關(guān)系.指出在a、b同時(shí)為偶數(shù)的情況下,定理1和定理2中關(guān)于聯(lián)結(jié)數(shù)的界可以更好,同時(shí)對(duì)新結(jié)論的最優(yōu)性進(jìn)行討論.本文的主要結(jié)論如下:

和

則G是分?jǐn)?shù)(f,n',m)-臨界消去圖.

定理3和定理4的證明主要運(yùn)用分?jǐn)?shù)(f,n',m)-臨界消去圖的充要條件，如下:

引理1[10]設(shè)G是一個(gè)圖,f是定義在V(G)上的非負(fù)整值函數(shù).設(shè)n'、m是兩個(gè)非負(fù)整數(shù).則G是分?jǐn)?shù)(f,n',m)-臨界消去圖當(dāng)且僅當(dāng)

對(duì)所有V(G)的不相交子集S,T成立,其中|S|≥n'.

2 定理3的證明

f(S)-f(T)+dG-S(T)≤bn'+2m-1

(1)

其中|S|≥n'.選取S、T使得|T|的值最小.從而對(duì)每個(gè)x∈T,都有dG-S(x)≤f(x)-1≤b-1成立.這是因?yàn)槿舸嬖谀硞€(gè)x∈T使得dG-S(x)≥f(x),則S和T{x}依然滿足(1).這與S和T的選取矛盾.

設(shè)d=min{dG-S(x):x∈T}.則0≤d≤b-1且

f(S)+dG-S(T)-f(T)≥a|S|+d|T|-b|T|

從而

bn'+2m-1≥a|S|-(b-d)|T|

(2)

選取x1∈T使得dG-S(x1)=d.我們從以下兩種情況分別得到矛盾.

情況1 1≤d≤b-1.

設(shè)Y=(V(G)S)NG-S(x1).則x1∈YNG(Y).從而Y≠?,NG(Y)≠V(G)且|NG(Y)|≥bind(G)|Y|.可知

n-1≥|NG(Y)|≥bind(G)|Y|=bind(G)(n-d-|S|)

即

(3)

由于a、b都是偶數(shù),可得

(4)

由(4),可知

(5)

記(5)式的左邊和右邊分別為A和B,則A-B>0.乘以(a+b-1)(a+b-d)進(jìn)行整理可得

0<(a+b-1)(a+b-d)(A-B)

=-(d-1)(an-(a+b-1)(a+b-d)-bn'-2m+2)

結(jié)合2≤d≤b-1,可知

情況2d=0.

在此情況下,首先給出如下斷言:

an-(a+b)-bn'-2m+3-(n-1)

=(a-1)n-(a+b)-bn'-2m+4

≥2(a+b-3)-(a+b)+4

=a+b-4≥0.

設(shè)h=|{x:x∈T,dG-S(x)=0}|且Y=V(G)S.由d=0,可知NG(Y)≠V(G).又根據(jù)T≠?知Y≠?.因此,|NG(Y)|≥bind(G)|Y|.從而有

n-h≥|NG(Y)|≥bind(G)|Y|=bind(G)(n-|S|)

所以

(6)

根據(jù)式(2)、式(6)、斷言1以及|T|≤n-|S|,得到

bn'+2m-1

≥f(S)+dG-S(T)-f(T)

≥a|S|+|T|-h-b|T|=a|S|-(b-1)|T|-h

≥a|S|-(b-1)(n-|S|)-h=(a+b-1)|S|-(b-1)n-h

=bn'+2m+(a+b)-4≥bn'+2m

矛盾.

f(S)+dG-S(T)-f(T)

=a|S|-(b-1)|T|

=bn'+2m-2

根據(jù)引理1,G不是分?jǐn)?shù)(f,n',m)-臨界消去圖.從而定理3的聯(lián)結(jié)數(shù)條件在a、b都是偶數(shù)的情況下是最好的.

3 定理4的證明

為證明定理4,首先給出如下關(guān)于分?jǐn)?shù)(f,n',m)-臨界消去圖鄰域條件的引理.

對(duì)每個(gè)非空獨(dú)立子集X?V(G)成立,且

則G是分?jǐn)?shù)(f,n',m)-臨界消去圖.

引理2的證明設(shè)G滿足引理2的條件但不是分?jǐn)?shù)(f,n',m)-臨界消去圖.顯然有T≠?.由引理1,存在不相交子集S和T滿足

f(S)-f(T)+dG-S(T)≤bn'+2m-1

(7)

其中|S|≥n'.選取S和T使|T|最小.從而有dG-S(x)≤f(x)-1≤b-1對(duì)每個(gè)x∈T都成立.

設(shè)d=min{dG-S(x)|x∈T},則

0≤d≤b-1,δ(G)≤d+|S|

(8)

根據(jù)式(8)以及a、b都是偶數(shù),可得

(9)

下面根據(jù)d的值分兩種情況討論.

情況1 1≤d≤b-1.

由于a和b都是偶數(shù),可知

(10)

根據(jù)式(9)和(10),得

(11)

將(11)式的左邊和右邊分別記為A和B,則有A-B>0.乘以(a+b-1)(a+b-d)后重新排列可得

0<(a+b-1)(a+b-d)(A-B)

=-(d-1)(an-(a+b-1)(a+b-d)-bn'-2m+2)

結(jié)合2≤d≤b-1,得到

(12)

情況2d=0.

設(shè)Y={x∈T|dG-S(x)=0}.顯然Y≠?且Y是獨(dú)立集.從而有

(13)

情況2.1 |S|+|T|≤n-1.

由式(7)及|S|+|T|≤n,得到

bn'+2m-1

≥f(S)+dG-S(T)-f(T)

≥a|S|+dG-S(T)-b|T|

≥a|S|+|T|-|Y|-b|T|

=a|S|-(b-1)|T|-|Y|

≥a|S|-(b-1)(n-1-|S|)-|Y|

=(a+b-1)|S|-(b-1)n-|Y|+b-1

≥(a+b-1)|S|-(b-1)n-|Y|+1

這說明

與式(13)矛盾.

情況2.2 |S|+|T|=n.

從式(7)和(9)中可知

bn'+2m-1

≥f(S)+dG-S(T)-f(T)

≥a|S|+dG-S(T)-b|T|

≥a|S|+|T|-|Y|-b|T|

=a|S|-(b-1)|T|-|Y|

≥a|S|-(b-1)(n-|S|)-|Y|

=(a+b-1)|S|-(b-1)n-|Y|

=bn'+2m-1

即

dG-S(T)=|T|-|Y|

(14)

且

a|S|+dG-S(T)-b|T|=bn'+2m-1

(15)

從而dG-S(T)是偶數(shù).這是因?yàn)閅?T.若|T|=|Y|,則由(14)可得dG-S(T)=0.若|T|>|Y|,則根據(jù)式(14)以及Y的定義可知dG-S(v)=1對(duì)每個(gè)v∈T-Y成立.由于|S|+|T|=n,得dG[T-Y](v)=1對(duì)每個(gè)v∈T-Y成立,且G[T-Y]是一個(gè)完美匹配.從而,|T|-|Y|是偶數(shù),同樣dG-S(T)也是偶數(shù).

因?yàn)閍和b都是偶數(shù),得a|S|+dG-S(T)-b|T|是偶數(shù),這與式(15)矛盾.

f(S)+dG-S(T)-f(T)

=bn'+2m-2

從而G不是分?jǐn)?shù)(f,n',m)-臨界消去圖.就這個(gè)意義上來說,引理2中的|NG(X)|條件是最好的.

下面給出定理4的證明.

定理4的證明設(shè)G滿足定理4的條件但不是分?jǐn)?shù)(f,n',m)-臨界消去圖.顯然T≠?.由引理1,存在不相交的子集S和T滿足

f(S)-f(T)+dG-S(T)≤bn'+2m-1

(16)

其中|S|≥n'.選取S和T使得|T|最小.則dG-S(x)≤f(x)-1≤b-1對(duì)所有x∈T成立.

對(duì)所有X?V(G),有X≠?且NG(X)≠V(G).設(shè)Y=V(G)NG(X).顯然?≠Y?V(G).

斷言2X∩NG(Y)=?.

斷言2的證明假設(shè)X∩NG(Y)≠?,x∈X∩NG(Y).由x∈NG(Y),得到y(tǒng)∈Y和xy∈E(G).

從而,y∈NG(x)?NG(X),這和y∈Y=V(G)NG(X)矛盾.

斷言3的證明運(yùn)用以上結(jié)果可得

|X|+|NG(Y)|≤n

(17)

和

NG(Y)≠V(G).

(18)

根據(jù)式(17)、(18)以及bind(G)的定義,可知

(19)

根據(jù)式(19),得到

(20)

從而

(21)

|NG(X)|

由此,斷言3成立.

(22)

即,

這和定理4的條件矛盾.

通過斷言3、斷言4和引理2,可知定理4成立.

參 考 文 獻(xiàn):

[1] BONDY J A,MUTRY U S R.Graph theory[M].Berlin:Spring,2008.

[2] 高煒,高云.關(guān)于聯(lián)結(jié)數(shù)與分?jǐn)?shù)(f,n',m)-臨界消去圖的幾個(gè)注記[J].云南師范大學(xué)學(xué)報(bào):自然科學(xué)版,2012,32(2):53-57.

[3] ZHOU S,SHEN Q.On fractional(f,n)-critical graphs[J].Information Processing Letters,2009,109(14):811-815.

[4] ZHOU S,BIAN Q,LIU H.A remark about fractional(f,n)-critical graphs[J].An.St.Univ.Qvidius Constanta,2011,19(1):365-372.

[5] GAO W,WANG W.Binding number and fractional(g,f,n',m)-critical deleted graph[J].Ars.Combin.,2014,CXIIIA:49-64.

[6] GAO W,WANG W.Anote on fractional(g,f,m)-deleted graphs[J].Ars.Combin.,2014,CXIIIA:129-137.

[7] GAO W,WANG W.A neighborhood union condition for fractional(k,m)-deleted graphs[J].Ars.Combin.,2014,CXIIIA:225-233.

[8] GAO W,WANG W.Degree conditions for fractional(k,m)-deleted graphs[J].Ars.Combin.,2014,CXIIIA:273-285.

[9] GAO W,LIANG L,XU T,et al.Tight toughness condition for fractional(g,f,n)-critical graphs[J].Journal of the Korean Mathematical Society,2014,51(1):55-65.

[10]高煒.關(guān)于分?jǐn)?shù)消去圖的若干結(jié)果[D]．蘇州:蘇州大學(xué),2012.