d-separated paths in hypercubes and star graphs

In this paper, we consider a generalized node disjoint paths problem: d-separated paths problem. In a graph G, given two distinct nodes s and t, two paths P and Q, connecting s and t, are d-separated if d_G-{s,t}⩾d for any u∈P-{s,t} and v∈Q-{s,t}, where d_G-{s,t}(u,v) is the distance between u and v in the reduced graph G-{s,t}. d-separated paths problem is to find as many d-separated paths between s and t as possible. In this paper, we give the following results on d-separated paths problems on n-dimensional hypercubes H_n and star graphs G_n. Given s and t in H_n, there are at least (n-2) 2-separated paths between s and t. (n-2) is the maximum number of 2-separated paths between s and t for d(s,t)⩾4. Moreover, (n-2) and separated paths of length at most d(s,t)+2 for d(s,t)<n and of length n for d(s,t)=n between s and t can be constructed in O(n²) optimal line. For d⩾3, d-separated paths in H_n do not exist. Given s and t in G_n, there are exactly (n-1) d-separated paths between s and t for 1⩽d⩽3 (n-1) 3-separated paths of length at most min{d(s,t)+4, d(G_n)+2} between s and t can be constructed in O(n²) optimal time, where d(G_n)=[3(n-1)/2]. For d⩾5 d-separated paths in G_n do not exist