Fault-Tolerant Path Embedding in Folded Hypercubes Under Conditional Vertex Constraints

The n-dimensional folded hypercube, denoted as FQn, is an extended version of the n-dimensional hypercube Qn, constructed by adding edges between opposite vertices in Qn, i.e., vertices with complementary addresses. Folded hypercubes outperform traditional hypercubes in various metrics such as the fault diameter, connectivity, and path length. It is known that FQn has bipartite characteristics in odd n≥3 and non-bipartite in even n≥2. In this paper, let FFv represent the set of faulty vertices in FQn and suppose that each vertex is adjacent to at least four fault-free vertices in FQn−FFv. Then, we consider the following path embedding properties: (1) For every odd n≥3, FQn−FFv contains a fault-free path with a length of at least 2n−2FFv−1 (respectively, 2n−2FFv−2) between any two fault-free vertices of odd (respectively, even) distance if FFv≤2n−5; (2) For every even n≥4, FQn−FFv contains a fault-free path with a length of at least 2n−2FFv−1 between any two fault-free vertices if FFv≤2n−6.