k元n立方體的條件容錯強Menger邊連通性

翟 登 鑫

(喀什大學 數學與統計學院, 新疆 喀什 844000)

1 預備知識

定義[7]設S?E(G),若圖G的子圖G-S中的每對點u和v能被min{degG-S(u);degG-S(v)}條無故障的邊不交路相連,其中degG-S(u)和degG-S(v)分別是子圖G-S中點u和v的度數,且|S|≤m,δ(G-S)≥2,則稱圖G是m條件容錯強Menger邊連通的.

圖1 4元-立方體Fig.1 Four-ary-cubes(a)—4元1立方體; (b)—4元2立方體.

2 引 理

引理1[8]設x與y是圖G中不同的兩點.x,y邊割的最小基數等于x,y邊不交路的最大數目.

證明 很容易驗證當n=2時,此引理成立.假設此引理在n-1時成立,n≥3,接下來證明對n也成立.

情形1 |S0|≤4n-9且|S1|≤4n-9.

事實上,若|S0|>2n-4,|S1|>2n-4,則|S|≥4n-6.由于|S|≤4n-5,故得到矛盾.因此,|S0|≤2n-4,|S1|≤2n-4.

情形1.1 |S0|≤2n-4且|S1|≤2n-4.

情形1.2 2n-3≤|S1|≤4n-9.

情形2 |S1|>4n-9.

證明 顯然,當n=3時此引理成立. 假設此引理n-1時成立,n≥4,接下來證明對n也成立.

情形1 |S0|≤5n-9且|S1|≤5n-9.

事實上,若|S0|>4n-9,|S1|>4n-9,則|S|≥8n-16.由于|S|≤5n-4,故得到矛盾.因此,|S0|≤4n-9,|S1|≤4n-9.

情形1.1 |S0|≤4n-9且|S1|≤4n-9.

情形1.1.1 |S0|≤2n-4且|S1|≤2n-4.

情形1.1.2 |S0|≤2n-4且2n-3≤|S1|≤4n-9.

情形1.1.3 2n-3≤|S0|≤4n-9且2n-3≤|S1|≤4n-9.

情形1.2 |S0|≤4n-9且4n-8≤|S1|≤5n-9.

情形1.2.1 |S0|≤n-1.

情形1.2.2 2n-3≤|S0|≤4n-9.

情形2 |S1|>5n-9.

3 主要結果

情形1 |V(C)|=kn-1.

情形2 |V(C)|=kn-2.

情形2.2 假設點u與點v不相鄰.