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不相邻.