边故障3元n立方体中的一对二点不交路覆盖
|
摘要
针对边故障Q■中一对二点不交路覆盖的问题,利用归纳假设法得到结论:当n≥2,边故障■时,在Q■中任取3个顶点x_0,y_1,y_2,则在Q■-F中有两条内部不交路P_1,P_2,使得V(P_1)∪V(P_2)=V(Q■),这里P_1连接x_0和y_1,P_2连接x_0和y_2,而且边故障■为最优上界.
In this paper, the following result is obtained. Let Q■ be the 3-ary n-cube, where n≥2, and F be a set of faulty edges with F≤2n-3, Assume that x,y_1 and y_2 be pairwise distinct vertices of Q■. Then there exist two vertex-disjoint paths P_1 between x_0 and y_1, P_2 between x_0 and y_2 such that V(P_1)∪V(P_2)=V(Q■). And the upper bound of 2n-3 edge faults tolerated is optimal.
In this paper, the following result is obtained. Let Q■ be the 3-ary n-cube, where n≥2, and F be a set of faulty edges with F≤2n-3, Assume that x,y_1 and y_2 be pairwise distinct vertices of Q■. Then there exist two vertex-disjoint paths P_1 between x_0 and y_1, P_2 between x_0 and y_2 such that V(P_1)∪V(P_2)=V(Q■). And the upper bound of 2n-3 edge faults tolerated is optimal.
引文
[1] X.B.Chen,Many-to-many disjoint paths in faulty hypercubes[J].Inform.Sci.2009,179(18) :3110–3115.
[2] Li X J ,Liu B ,Ma M ,et al.Many-to-many disjoint paths in hypercubes with faulty vertices [J].Discrete Applied Mathematics,2016,217(P2):229-242.
[3] Cheng-Nan Lai,An efficient construction of one-to-many node-disjoint paths in folded hypercubes,J.Parallel Distrib.Comput.2014,(7):2310–2316.
[4] Yang M C ,Tan J J M ,Hsu L H .Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes.[J].Journal of Parallel Distributed Computing,2007,67(4):362-368.
[5] Zhang S ,Wang S .Many-to-many disjoint path covers in k-ary n-cubes[J].Theoretical Computer Science,2013,491(C):103–118.
[6] 佘卫强,点故障3-ary n 立方体中经过指定路的无故障哈密尔顿圈[J].佳木斯大学学报,2015,9(5):749-750.
[7] X.B.Chen,Paired 2-disjoint path covers of faulty k-ary n-cubes[J].Theoretical Computer Science,2016,609(C):494–499.
[8] J.A.Bondy,U.S.R.Murty,Graph Theory with Applications[M].Macmillan Press,London,1976.
[2] Li X J ,Liu B ,Ma M ,et al.Many-to-many disjoint paths in hypercubes with faulty vertices [J].Discrete Applied Mathematics,2016,217(P2):229-242.
[3] Cheng-Nan Lai,An efficient construction of one-to-many node-disjoint paths in folded hypercubes,J.Parallel Distrib.Comput.2014,(7):2310–2316.
[4] Yang M C ,Tan J J M ,Hsu L H .Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes.[J].Journal of Parallel Distributed Computing,2007,67(4):362-368.
[5] Zhang S ,Wang S .Many-to-many disjoint path covers in k-ary n-cubes[J].Theoretical Computer Science,2013,491(C):103–118.
[6] 佘卫强,点故障3-ary n 立方体中经过指定路的无故障哈密尔顿圈[J].佳木斯大学学报,2015,9(5):749-750.
[7] X.B.Chen,Paired 2-disjoint path covers of faulty k-ary n-cubes[J].Theoretical Computer Science,2016,609(C):494–499.
[8] J.A.Bondy,U.S.R.Murty,Graph Theory with Applications[M].Macmillan Press,London,1976.