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

崔藝蘭，歐見平

（五邑大學 數學與計算科學學院，廣東 江門 529020）

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

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

1 預備引理

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

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

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

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

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

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

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

2 極大限制邊連通性

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

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

1）若α≤-1 且，則.

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

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

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

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

同理，

由引理1，可得

所以，

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

矛盾.

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

矛盾.

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

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

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

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

由引理2，可得

同理，

由引理2，可得

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

矛盾. 定理證畢.

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

1）若α≤-1 且，則.

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

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

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

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

由引理1，可得

同理，

由引理1，可得

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

矛盾.

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

矛盾.

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

矛盾. 定理證畢.

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

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

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

由引理2，可得

同理

由引理2，可得

因為0＜α＜ 1，所以

且

矛盾. 定理證畢.