边故障超立方体中两条无故障点不交路

Two Fault-free Vertex-disjoint Paths in a Hypercube with Faulty Edges

文中用归纳假设法证明了结论:当n≥3时,令超立方体中的边故障集∣F∣≤n-3,设x1,x2,y1,y2是Qn中4个顶点,使得距离d(x1,y1)和距离d(x2,y2)都是奇数,则在Qn-F中存在两条路P1和P2,使得V(P1)∩V(P2)=φ,V(P1)∪V(P2)=V(Qn),这里P1连接x1和y1,P2连接x 2和y 2,而且边故障集∣F∣=n-3(n≥3)是最佳上界.

In this paper, the following result is obtained. Let Qn be the n --cube, where n≥ 3, and F be any subset of edges with ｜F｜≤n-3 . Assume thai x1,x2,y1 and y2 be pairwise distinct vertices of Qn such that both the distance d（x1,y1） and d（x2,y2 ） are odd. Then there exist fault-free paths P1 between x1 and y1 and P2 between x1 and y2 such thatal V（P1）∩V（P2）=φ and V（P1）∪V（P2）=V（Qn）. The upper bound n= 3 number of faulty edges is optimal.