k元n立方體的條件容錯(cuò)強(qiáng)Menger邊連通性

翟 登 鑫

(喀什大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 新疆 喀什 844000)

1 預(yù)備知識(shí)

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

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

2 引 理

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

證明 很容易驗(yàn)證當(dāng)n=2時(shí),此引理成立.假設(shè)此引理在n-1時(shí)成立,n≥3,接下來(lái)證明對(duì)n也成立.

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

事實(shí)上,若|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.

證明 顯然,當(dāng)n=3時(shí)此引理成立. 假設(shè)此引理n-1時(shí)成立,n≥4,接下來(lái)證明對(duì)n也成立.

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

事實(shí)上,若|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 主要結(jié)果

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

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

情形2.2 假設(shè)點(diǎn)u與點(diǎn)v不相鄰.