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

The n -dimensional folded hypercube, denoted as F Q n , is an extended version of the n -dimensional hypercube Q n , constructed by adding edges between opposite vertices in Q n , 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 F Q n has bipartite characteristics in odd n ≥ 3 and non-bipartite in even n ≥ 2 . In this paper, let F F v represent the set of faulty vertices in F Q n and suppose that each vertex is adjacent to at least four fault-free vertices in F Q n − F F v . Then, we consider the following path embedding properties: (1) For every odd n ≥ 3 , F Q n − F F v contains a fault-free path with a length of at least 2 n − 2 F F v − 1 (respectively, 2 n − 2 F F v − 2 ) between any two fault-free vertices of odd (respectively, even) distance if F F v ≤ 2 n − 5 ; (2) For every even n ≥ 4 , F Q n − F F v contains a fault-free path with a length of at least 2 n − 2 F F v − 1 between any two fault-free vertices if F F v ≤ 2 n − 6 .