基于廣義Randi?指數(shù)的限制邊連通性的研究

崔藝蘭，歐見平

（五邑大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，廣東 江門 529020）

為了更準(zhǔn)確估計和比較網(wǎng)絡(luò)的可靠性，文獻(xiàn)[7-8]介紹了m限制邊割和m限制邊連通度的概念:圖G的邊割S是一個m限制邊割，如果G-S的每個連通分支都至少含有m個點(diǎn). 所有m限制邊割中所含的最小邊數(shù)稱為圖G的m限制邊連通度，用λm(G)表示，或簡寫為λm. 如果連通圖G含有m限制邊割，則稱它是λm連通的. 令，其中表示圖G中只有一個端點(diǎn)在X的邊的集合，簡寫為. 如果，則圖G是λm最優(yōu)的或極大m限制邊連通的. 注意到當(dāng)m= 1時，是邊連通度；當(dāng)m= 2時，是限制邊連通度，也常表示為λ＇；當(dāng)m= 3時是3 限制邊連通度λ3. 極大3 限制邊連通在網(wǎng)絡(luò)設(shè)計的可靠性中發(fā)揮著重要的作用，一些極大3 限制邊連通的充分條件可以在文獻(xiàn)[9-10]中得到. 極大m限制邊連通也取得了豐碩的成果，讀者可參考文獻(xiàn)[7-8]等.

Li 等[11]在2005 年定義了零階廣義Randi? 指數(shù)：，其中α是實數(shù)，d(v) 是點(diǎn)v的度. 特別地，當(dāng)α=-1 時，，即為圖G的逆度. 許多研究者給出了基于零階廣義Randi? 指數(shù)，階數(shù)和最小度的最優(yōu)λ(G)圖和超級λ(G)圖的充分條件[12-16]. 郭利濤等[17-19]還給出了關(guān)于R(G) ,δ(G) ,ξ(G)和n的函數(shù)的圖是最優(yōu)λ2和最優(yōu)λ3的充分條件. 本文將他們的結(jié)論推廣到限制邊連通圖上，分別考慮在一定條件下，基于零階廣義Randi? 指數(shù)分別給出了圍長g≥ 5、δ≥2的圖是λ2最優(yōu)及g≥ 6、δ≥ 2的圖是λ3最優(yōu)的充分條件. 對于未說明的其他符號和術(shù)語，我們采用文獻(xiàn)[20]中的符號與術(shù)語.

1 預(yù)備引理

為了得到主要結(jié)論，我們將列出用于后面證明的一些引理.

引理1[12]設(shè)實數(shù)α＜0或者α＞ 1且x1,x2, … ,xp和A為正實數(shù)使得，則.如果x1,x2, … ,xp和A為正整數(shù)且A=ap+b，其中a,b是整數(shù)且0≤b＜p，則.

引理2[13]設(shè)實數(shù)0＜α＜ 1且x1,x2, … ,xp和A為正實數(shù)使得，則. 如果x1,x2, … ,xp和A為正整數(shù)且A=ap+b，其中a,b是整數(shù)且0≤b＜p，則.

以下這個引理來自凸函數(shù)和凹函數(shù)的定義.

引理3[17]設(shè) Φ (x)是［L,R］上的連續(xù)函數(shù)且l+r=L+R，其中l(wèi),r∈［L,R］. 則

引理4[18]設(shè)G是圍長大于等于5 的λ2連通圖，且δ(G) ≥ 2，則存在一個λ2割［X,Y］，其中兩個不交點(diǎn)集且［X,Y］ =λ2. 如果λ2＜ξ，則.

引理 5[19]設(shè)G是λ3連通圍長大于等于 6 的圖，且δ(G) ≥ 2. 如果，則存在一個λ3割［X,Y］，其中兩個不交點(diǎn)集，使得.

2 極大限制邊連通性

接下來我們考慮在一定條件下，圖G是2λ最優(yōu)及3λ最優(yōu)的充分條件.

定理1設(shè)G是圍長g(G) ≥5 的2λ連通n階圖且最小度δ≥2 .

1）若α≤-1 且，則.

2）若 -1 ＜α＜ 0且，則.

3）若1＜α≤ 2且，則.

證明反設(shè)，則圖G存在一個最小2 限制邊割S=[X,Y]，其中,X,Y是兩個不交的點(diǎn)集使得，且. 根據(jù)引理 4 可知，，所以. 不失一般性，設(shè)圖G的最小度為δ的一個點(diǎn).

由于X中的每個點(diǎn)至多能與X中的個點(diǎn)相連，且X中的點(diǎn)僅與Y中的點(diǎn)有λ2條邊相連.則

同理，

由引理1，可得

所以，

當(dāng)α≤- 1時，，且. 由于，容易驗證 當(dāng)t＞1,α≤-1 時，，所以 此時g(t)為凹函數(shù). 又由假 設(shè)，則有

矛盾.

當(dāng) - 1＜α＜ 0時，，且. 由于，容易驗證當(dāng)t＞ 1, -1＜α＜ 0時，，所以此時g(t)也為凹函數(shù). 又由假設(shè)，則有

矛盾.

當(dāng)1＜α≤ 2時，，且. 同 樣 容 易 驗 證 當(dāng)t＞1,1＜α≤ 2時，，所以g(t)為凹函數(shù). 又由假設(shè)，得

定理 2設(shè)G是圍長g(G) ≥ 5的λ2連通n階圖且最小度δ≥ 2. 若0＜α＜ 1且，則.

證明反設(shè)，則圖G存在一個最小2 限制邊割S=[X,Y]，其中,X,Y是兩個不交的點(diǎn)集使得，且. 根據(jù)引理 4 可知，，所以. 不失一般性，設(shè)圖G的最小度為δ的一個點(diǎn).

由于X中的每個點(diǎn)至多能與X中的X- 1個點(diǎn)相連，且X中的點(diǎn)僅與Y中的點(diǎn)有λ2條邊相連.則

由引理2，可得

同理，

由引理2，可得

所以，.因為0＜α＜ 1，所以. 令函數(shù)，容易驗證當(dāng)，所以此時g(t)為凸函數(shù)，根據(jù)引理3，可得

矛盾. 定理證畢.

定理3設(shè)G是圍長g(G) ≥ 6且最小度δ(G) ≥ 2的λ3連通n階圖.

1）若α≤-1 且，則.

2）若 -1 ＜α＜ 0且，則.

3）若1＜α≤ 2且，則.

證明反設(shè)，則圖G存在一個最小3 限制邊割S=[X,Y]，其中,X,Y是兩個不交的點(diǎn)集使得，且. 根據(jù)引理 5 可知，，所以. 不失一般性，設(shè)圖G的最小度為δ的點(diǎn).

由于X中的每個點(diǎn)至多能與X中的個點(diǎn)相連，且X中的點(diǎn)僅與Y中的點(diǎn)有λ3條邊相連.則

由引理1，可得

同理，

由引理1，可得

當(dāng)α≤-1 時，容易驗證g(t)為凹函數(shù)且

矛盾.

當(dāng) -1 ＜α＜ 0時，容易驗證g(t)也為凹函數(shù)且

矛盾.

當(dāng)1＜α≤ 2時，容易驗證g(t)為凹函數(shù)且

矛盾. 定理證畢.

定理4設(shè)G是圍長g(G) ≥ 6且最小度δ(G) ≥ 2的n階λ3連通圖. 若0＜α＜ 1且,則.

證明反設(shè)，則圖G存在一個最小3 限制邊割S=[X,Y]，其中,X,Y是兩個不交的點(diǎn)集使得，且. 根據(jù)引理 5 可知，，所以. 不失一般性，設(shè)圖G的最小度為δ的一個點(diǎn).

由于X中的每個點(diǎn)至多能與X中的個點(diǎn)相連，且X中的點(diǎn)僅與Y中的點(diǎn)有λ3條邊相連.則

由引理2，可得

同理

由引理2，可得

因為0＜α＜ 1，所以

且

矛盾. 定理證畢.