WorksComputer Science
Fault-tolerant Hamiltonian connectivity of Johnson graphs
Abstract
Johnson graphs are a classical family of highly symmetric networks known to be Hamiltonian-connected in the fault-free setting. In this paper, we investigate their Hamiltonian connectivity under three failure models, namely general edge faults, matching faults, and vertex faults. For general edge faults, we prove that remains Hamiltonian-connected after the deletion of any set of at most edges for . Since is -regular, this attains the natural degree-based upper bound for Hamiltonian connectivity. We then consider matching faults, which exclude the concentration of multiple faulty links at a single vertex and permit substantially larger fault sets. We show that remains Hamiltonian-connected after the deletion of an arbitrary matching for , including a perfect matching whenever one exists. For vertex failures, we prove that is -vertex-fault-tolerant Hamiltonian-connected for . All three results are constructive and lead to recursive fault-tolerant Hamiltonian routing algorithms. Simulation results on Johnson graphs with up to vertices further show that the routing algorithms successfully construct fault-free Hamiltonian paths for all tested source-destination pairs, with measured execution times exhibiting near-linear growth with network size. These results establish a unified fault-tolerant Hamiltonian-connectivity framework for Johnson graphs under different failure patterns.
Introduction
Johnson graphs form an important family of highly symmetric graphs with rich combinatorial and algebraic structures. For integers and with , the Johnson graph has all -subsets of as its vertices, where two vertices are adjacent whenever their intersection has size . Thus, has vertices and is -regular. Owing to their vertex-transitivity and distance-regularity [1], Johnson graphs have received considerable attention in algebraic graph theory [2, 3, 4], combinatorial and Hamiltonian properties [5, 6], and studies of highly symmetric network topologies [7, 8].
A wide range of algorithms for high-performance computing rely on processor organizations with linear arrays and rings. These structures therefore provide natural models for communication, control, and data organization in parallel and distributed systems [9]. In graph-theoretic terms, a linear array spanning all processors corresponds to a Hamiltonian path, which visits every vertex exactly once. A network is said to be Hamiltonian-connected if such a spanning path exists between every pair of distinct vertices. The use of Hamiltonian paths in multicast routing can help reduce the likelihood of deadlocks and alleviate network congestion [10]. In addition, Ye and Liang [11] proposed a five-round adaptive fault-diagnosis algorithm for distributed-memory multiprocessors that relies on a Hamiltonian interconnection topology. Consequently, Hamiltonian properties have been extensively studied for a variety of interconnection networks. Among them, Hamiltonian connectivity represents a particularly strong spanning-path property and has been established for hypercube variants [12, 13, 14, 15, 16], -star graphs [17], arrangement graphs [18], and cycle composition networks [19]. For Johnson graphs, Alspach [20] proved that is Hamiltonian-connected, establishing this strong spanning-path property in the fault-free setting.
In practical networks, however, processors and communication links may fail, making it important to determine whether Hamiltonian connectivity can be maintained in the presence of faults. Under general edge faults, the locations of faulty links are unrestricted, and fault-tolerant Hamiltonian properties under this model have been extensively investigated for various interconnection networks [21, 22, 23, 24, 25]. Consequently, determining the maximum number of general edge faults that can be tolerated while preserving Hamiltonian connectivity is a fundamental problem in the reliability analysis of interconnection networks.
Beyond the unrestricted fault model, a variety of constrained edge-fault models that exclude certain local obstructions or restrict the distribution of faulty links have also been investigated, including conditional fault models [14, 26, 27], in which a prescribed minimum residual degree is required, as well as more recent partitioned-edge [28] and region-based fault models [29]. These studies show that incorporating information about the distribution of faults can yield stronger fault-tolerance guarantees for Hamiltonian connectivity.
A natural way to accommodate a substantially larger number of link failures is to restrict the faulty edges to be pairwise disjoint, i.e., a matching. Such a restriction prevents multiple faulty links from concentrating at a single vertex. Hamiltonian properties under matching faults have therefore received considerable attention in hypercube-based networks. Dimitrov et al. [30] characterized Hamiltonian paths and cycles in hypercubes avoiding a prescribed matching in terms of certain forbidden half-layer and almost-layer structures. Dybizbański and Szepietowski [31] further studied hypercubes with pairwise disjoint faulty edges and showed that, for , is Hamiltonian if and only if every dimension contains two fault-free crossing edges of different parity. For the balanced hypercube , Lan and Lü [32] proved that every fault-free edge lies on a fault-free Hamiltonian cycle even when the faulty-edge set is a perfect matching. Similarly, Zuo and Lü [33] showed that, for any matching of the folded hypercube , remains Hamiltonian for and is Hamiltonian laceable for every odd . In particular, in both and , the number of admissible faulty edges can reach and , respectively, both exponential in the network dimension .
Whereas an edge fault disables a single communication link, a vertex fault removes a processor together with all of its incident links and can therefore affect the network more extensively. Accordingly, vertex failures have been studied both independently and together with edge failures in mixed fault models. In particular, fault-tolerant Hamiltonian properties under combined vertex and edge failures have been established for several interconnection networks, including -bubble sort graphs [34], 2-tree-generated networks [35], and arrangement graphs [18]. These results further motivate the study of Hamiltonian connectivity under vertex failures in Johnson graphs.
For bipartite networks, Hamiltonian laceability serves as the natural counterpart of Hamiltonian connectivity because the bipartition imposes parity restrictions on the endpoints of a Hamiltonian path. To provide a comparison with representative results for several well-known interconnection networks, Table 1 summarizes fault-tolerant Hamiltonian properties under different failure models.
| Network | Bipartite | Hamiltonian Property | Fault Model | Fault-Tolerance Result |
| Hypercube | Yes | Hamiltonian Laceability<br>Hamiltonicity | General Edge<br>Matching | [24]<br>Dimension-parity condition [31] |
| Balanced Hypercube | Yes | Hamiltonian Laceability<br>Hamiltonicity | General Edge<br>Matching | [25]<br>general matching [32] |
| Folded Hypercube (odd ) | Yes | Strongly Hamiltonian Laceability<br>Hamiltonian Laceability | General Edge<br>Matching | [36]<br>Arbitrary matching [33] |
| Star Graph | Yes | Hamiltonian Laceability | General Edge | [37] |
| -ary -cube ( even) | Yes | Hamiltonian Laceability | General Edge | [38] |
| -Star Graph () | No | Hamiltonian Connectivity | Mixed Vertex/Edge | [17] |
| Arrangement Graph | No | Hamiltonian Connectivity | Mixed Vertex/Edge | [18] |
| -Bubble Sort Graph | No | Hamiltonian Connectivity | Mixed Vertex/Edge | [34] |
| 2-tree-generated network | No | Hamiltonian Connectivity | Mixed Vertex/Edge | [35] |
| Johnson | No | Hamiltonian Connectivity | General Edge<br>Matching<br>Vertex | <br>Arbitrary matching<br> |
Table 1. Comparison of fault-tolerant Hamiltonian properties of representative interconnection networks.
Despite the extensive literature on fault-tolerant Hamiltonian properties of well-known interconnection networks, corresponding results for Johnson graphs remain relatively limited. In particular, the following questions arise naturally. First, how many arbitrarily distributed faulty edges can tolerate while remaining Hamiltonian-connected? Second, if the faulty edges are required to form a matching, can Hamiltonian connectivity be preserved for fault sets far exceeding this general-fault bound, possibly even for a perfect matching? Finally, how robust is the Hamiltonian connectivity of Johnson graphs against vertex failures? In this paper, we answer these questions constructively. Our main contributions are summarized as follows.
General edge faults. We prove that remains Hamiltonian-connected for every edge-fault set satisfying . Since
Note: and denote the sets of faulty vertices and faulty edges, respectively.
is -regular, this bound reaches the natural upper bound imposed by the minimum-degree obstruction.
Matching faults. We establish that remains Hamiltonian-connected after the deletion of an arbitrary matching. In particular, the result still holds when the faulty edges form a perfect matching whenever one exists. Thus, under this model, the number of faulty links can reach , i.e., half the order of .
Vertex faults. We show that is -vertex-fault-tolerant Hamiltonian-connected; that is, after the removal of any set of at most faulty vertices, each pair of remaining fault-free vertices can still be joined by a Hamiltonian path covering all fault-free vertices.
Constructive routing algorithms. The constructive proofs lead directly to recursive fault-tolerant Hamiltonian routing algorithms for the three fault models. We further analyze their complexity and evaluate their practical execution time through simulations on Johnson graphs of different scales.
These results establish a systematic fault-tolerant Hamiltonian-connectivity framework for Johnson graphs and demonstrate their strong resilience in supporting Hamiltonian routing under diverse failure scenarios.
The remainder of this paper is organized as follows. Section II introduces the necessary notations and basic properties of Johnson graphs, and then investigates Hamiltonian connectivity under general edge faults. Section III establishes the fault-tolerant Hamiltonian connectivity under arbitrary matching faults. Section IV studies vertex faults and derives the corresponding vertex-fault-tolerant Hamiltonian-connectivity result. Section V develops the Hamiltonian routing algorithms associated with the three fault models, together with their complexity analysis and performance evaluation. Finally, Section VI concludes the paper.
Optimal Edge-fault-tolerant Hamiltonian Connectivity of
We first introduce some notation and preliminary results that will be used throughout this paper. For a fixed element , let denote the subgraph of induced by the vertices containing , and let denote the subgraph induced by the vertices not containing . When the choice of is clear from the context, we simply write and . Clearly, and . For an edge-fault set , let and denote the sets of faulty edges contained in and , respectively. We also recall that for , and .
Lemma 1. [20] For and , is Hamiltonian-connected.
Lemma 2. [7] , for and , is paired 2-coverable.
Lemma 3. [26] Let satisfy . Then is Hamiltonian-connected whenever for ; the corresponding maximum bounds for are 0, 2, 5, and 9, respectively.
As a direct consequence of Lemma 3, we obtain the following edge-fault Hamiltonian-connectivity result for complete graphs.
Corollary 4. For , is -edge-fault-tolerant Hamiltonian-connected.
Proof. Let be any faulty edge set with . Since every vertex of has degree ,
Thus, the minimum-degree condition in Lemma 3 is satisfied.
It remains to verify that the number of faulty edges is within the corresponding bound given in Lemma 3. If and , then . For the exceptional cases , we have , respectively, which do not exceed the corresponding bounds 0, 2, 5, 9 given in Lemma 3. Therefore, is Hamiltonian-connected.
We now turn our attention to the Johnson graphs. For small parameters, although the graphs are relatively small, manually checking all possible faulty-edge sets and all pairs of endpoints is still combinatorially tedious. Therefore, we developed an exhaustive-search program to rigorously verify the base cases. For each admissible faulty-edge set , we enumerate all pairs of distinct vertices and exhaustively verify the existence of a Hamiltonian - path in .
Lemma 5. is 1-edge-fault-tolerant Hamiltonian-connected.
Since , by computationally verifying , we immediately obtain the following lemma.
Lemma 6. Both and are 3-edge-fault-tolerant Hamiltonian-connected.
Before presenting our main result, we first note a natural upper bound for edge-fault Hamiltonian connectivity. Let be a graph with minimum degree . If edges incident with a vertex fail, then has only two fault-free neighbors, say and . Any Hamiltonian path joining and would necessarily contain the subpath , preventing the path from spanning the remaining vertices. Hence, the ordinary edge-fault Hamiltonian-connectivity bound of cannot exceed . Since is -regular, its edge-fault Hamiltonian-connectivity bound is at most . We next show that this upper bound is attained by Johnson graphs.
Theorem 7. For , , is -edge-fault-tolerant Hamiltonian-connected.
Proof. Let be a set of faulty edges in satisfying . It follows from Corollary 4, and Lemmas 5 and 6, that the statement holds for , with , and for , and .
When considering with and , the induction hypotheses are: is -edge-fault-tolerant Hamiltonian-connected whenever and , or is -edge-fault-tolerant Hamiltonian-connected whenever and .
Case 1. . Then . Since , the induction hypothesis applied to yields that is -edge-fault-tolerant Hamiltonian-connected. Hence, has the same property.
Case 2. . Let
We claim that . Suppose on the contrary that . Then
Since the two endpoints of each edge share common elements, the sum counts each edge at most times. Thus,
Since , we have
Note that , so we have
Hence, the claim holds.
Given that , define . Consequently, . Next, we demonstrate by contradiction that must contain at least one element such that , except for the case where and . Suppose no such exists in . Then,
If an edge is contained in , then the two endpoints of the edge do not contain . Since the union of the -sets corresponding to the endpoints of one edge contains elements, the sum counts each edge at most times. Then
Note that and .
(1) If or , we have , which implies . Thus,
which contradicts the assumption that .
(2) If and , we have , which yields
This implies that and . If (i.e., ), then
which is impossible since .
Therefore, except for the case and , there exists an element such that
Fix such an element , and write and in what follows.
Let and be any two distinct vertices of . We distinguish the following cases according to the locations of and in the induced subgraphs and . For the case with , if there exists an element such that the faulty edge sets of the two induced subgraphs and determined by satisfy the above inequality, then the desired result follows directly by induction. Otherwise, Lemma 8 establishes that remains 6-edge-fault Hamiltonian-connected.
Case 2.1. . By the induction hypothesis, there exists a Hamiltonian path joining and in , which we denote by , where . For and , we have
This implies that there exist two non-faulty edges and such that and . By the induction hypothesis, there exists a Hamiltonian path joining and in , denoted by . Then is a Hamiltonian path joining and in .
Case 2.2. . By the induction hypothesis, there exists a Hamiltonian path joining and in , denoted by , where . For and , we have
This implies that there exist two non-faulty edges and such that and . By the induction hypothesis, there exists a Hamiltonian path joining and in , denoted by . Then is a Hamiltonian path joining and in .
Case 2.3. and . Let . Then
This implies that there exists an edge . By the induction hypothesis, there exists a Hamiltonian path joining and (resp. and ) in (resp. ), denoted by (resp. ). Clearly, the path is a Hamiltonian path joining and in .
In the following lemma, we deal with the exceptional case from Theorem 7.
Lemma 8. Let with , and define
Suppose and for every . Then is Hamiltonian-connected.
Proof. Since two adjacent vertices of share exactly two elements, each faulty edge is counted exactly twice in . Hence,
Since , it follows that . Moreover, equality holds throughout. Consequently,
and no faulty edge is counted by for any . Thus, the two common elements of the endpoints of every faulty edge belong to . Without loss of generality, let and . For convenience, let () denote the set of elements common to the two endpoints of the -th faulty edge in . By the definition of , among the six sets , at least four contain the element 1, at least four contain the element 2, and at least four contain the element 3. Since the total number of elements in the six sets is exactly 12, it follows that there are exactly two sets containing , exactly two sets containing , and exactly two sets containing . On the other hand, by the assumption, for any , we have . Since cannot be a common element of the two endpoints of a faulty edge, each can occur in at most two endpoints of faulty edges. Therefore, the number of endpoints containing elements from is at most six. Consequently, at least six endpoints correspond to vertices containing the elements . Since all these vertices are endpoints of faulty edges, the 12 endpoints must consist of six copies of , two vertices containing 4, two vertices containing 5, and two vertices containing 6. It is straightforward to verify that all such configurations are isomorphic to one another. Hence, we may assume that , , , , , , , and .
Let and be any two distinct vertices of . We now discuss the following cases based on the distribution of these vertices in and . It is clear that .
Case 1. . Then has only one vertex .
Case 1.1. , say . Note that . Let . Since contains exactly four edges entirely within , leaves exactly three faulty edges in . By Lemma 6, is 3-edge-fault-tolerant, so there exists a Hamiltonian path in joining and , denoted by . Choose a vertex such that . Since is a 6-regular graph on ten vertices, the vertex-deleted subgraph has nine vertices with a minimum degree of five. By the classic Ore-type condition for Hamiltonian connectivity (), remains Hamiltonian-connected. Thus, there exists a Hamiltonian path in joining and , denoted by . Then the path is a Hamiltonian path in joining and .
Case 1.2. . Note that has exactly three neighbors in . Since we only need to avoid the two vertices and , there exists at least one neighbor of in that is neither nor . Choose such a vertex as . By Lemma 2, there exist two vertex-disjoint paths and of that cover . Adding the fault-free cross edges and , and concatenating , , and yields a Hamiltonian path in joining and .
Case 2. . Recall that leaves exactly 3 faulty edges in . By Lemma 6, there exists a Hamiltonian path in joining and . However, might contain the faulty edge . We discuss the following two subcases based on whether is contained in .
Case 2.1. . We choose two distinct vertices such that and . By Lemma 1, there exists a Hamiltonian path in joining and . By deleting the edge , adding the edges and , and concatenating these segments with , we obtain a Hamiltonian path in joining and .
Case 2.2. . Then choose any edge and two distinct vertices such that and . By Lemma 1, there exists a Hamiltonian path in joining and . By deleting the edge , adding the cross edges and , and concatenating the resulting segments of with , we obtain a Hamiltonian path in joining and .
Case 3. and . Choose . By Table 2, there exists a Hamiltonian path in joining and , denoted by . For any , by Lemma 1, there exists a Hamiltonian path in joining and , denoted by . Then the path is a Hamiltonian path in joining and .
| Hamiltonian path | ||
| 125 | 123 | |
| 125 | 126 | |
| 125 | 135 | |
| 125 | 136 | |
| 125 | 156 | |
| 125 | 235 | |
| 125 | 236 | |
| 125 | 256 | |
| 125 | 356 |
Table 2. Hamiltonian paths in joining and all other vertices in . For convenience, the set is abbreviated as .
Edge-fault-tolerant Hamiltonian Connectivity of under Matching Faults
In the previous section, we showed that under unrestricted edge faults, the maximum number of faulty edges that can be guaranteed while preserving Hamiltonian connectivity of is . This worst-case bound is determined by fault configurations highly concentrated around a single vertex. To investigate whether substantially larger fault sets can be tolerated when such concentration is excluded, we next consider matching faults, where no two faulty edges share a common endpoint. In this section, we prove that Hamiltonian connectivity is preserved after the deletion of an arbitrary matching.
We first consider the base cases for small networks.
Lemma 9. For any two adjacent vertices and of and any matching , the graph contains a Hamiltonian path joining and .
Proof. Since and are adjacent in , there exists an element . Let and . Then and . Write and , where the vertices are indexed so that for . Hence, . Since , , and , by relabeling the indices if necessary, we may assume that , . The decomposition of into two copies of , together with the corresponding cross edges, is illustrated in Figure 1.
Figure 1. Structure of under the partition , where and if and only if .
Case 1. . In this case, all edges of and are fault-free. Consider the two cross edges and . Since they share the vertex and is a matching, at most one of them belongs to . If , then is a Hamiltonian path from to in . If , then , and hence is a Hamiltonian path from to in .
Case 2. .
By interchanging the roles of and if necessary, we may assume that . Since and is a matching, . Extend to a maximal matching of . Because the unique edge of is incident with two of the three vertices of , each of the other two edges of shares an endpoint with it. Consequently, no additional edge of can be added when extending , and therefore . Moreover, if a Hamiltonian path from to exists in , then the same path also lies in , since . Thus, it suffices to consider maximal matchings satisfying .
Note that is isomorphic to the octahedral graph. With the terminals fixed as and , there are exactly nine maximal matchings satisfying : six perfect matchings of size 3 and three maximal matchings of size 2. By the symmetry of and the automorphisms preserving the terminal set , the nine maximal matchings can be reduced to four essentially different configurations up to isomorphism. These four representative matchings, together with their corresponding fault-free Hamiltonian paths from to , are listed in Table 3. Therefore, contains a Hamiltonian path from to in each case, and hence so does .
| Size | Faulty maximal matching | Hamiltonian path |
| 3 | ||
| 3 | ||
| 2 | ||
| 2 |
Table 3. Hamiltonian paths in joining and for all essentially different maximal matching faults.
Lemma 10. is matching-fault-tolerant Hamiltonian-connected.
Proof. Let and be two distinct vertices of , and let be a set of faulty edges that forms a matching in . Since , there exists an element such that and . Clearly, and , with and .
Since and is a matching, always contains a cycle of length four. Consequently, there exists a Hamiltonian path in starting at , which we denote by .
Next, we need to find a fault-free edge from to a vertex such that is adjacent to in . Let for some element . Since consists of all 2-subsets of , the vertex can be written as where . The neighbors of lying in consist of exactly three vertices, all of which contain . We consider two cases based on whether .
If , say , then is itself a neighbor of in . The other two neighbors of in must be of the form and where . So they are adjacent to in . If , let . The three neighbors of in are , , and . Notice that and each share exactly one element with , meaning they are adjacent to in .
In both cases, has at least two neighbors in that are adjacent to . Since is a matching, at most one edge incident to belongs to . Thus, there exists at least one fault-free edge from to a vertex such that is adjacent to . By Lemma 9, there exists a Hamiltonian path in joining and . By adding the fault-free edge and concatenating the path with , we obtain a Hamiltonian path in joining and .
We are now ready to present the main result of this section.
Theorem 11. For and , is matching-fault-tolerant Hamiltonian-connected.
Proof. We prove the theorem by induction on .
For , since , let be a matching in , and let be the set of vertices not incident to any edge of . By symmetry, we enumerate Hamiltonian paths of essentially different terminals in Table 4. Since , the result also holds for . For and , the result follows from Lemma 10.
| Terminal pair | Hamiltonian path in | |
| 1 | ||
| 2 | ||
| 3 | ||
| 4 |
Table 4. Hamiltonian paths for all representative terminal pairs in under a matching fault.
Now assume that and , and suppose that is matching-fault-tolerant Hamiltonian-connected for every and .
Since , we may assume that . Let be any matching of , and let be any two distinct vertices of . Since , there exists an element . Let and . Then , . Choose any vertex . Since contains , it has exactly neighbors in . Hence
Since is a matching, at most one edge incident with belongs to . Therefore, among the edges joining to , there exists a non-faulty edge for some .
The restriction of to is a matching, and similarly is a matching. By the induction hypothesis, there exists a Hamiltonian path in , and a Hamiltonian path in . Since , concatenating these paths with the edge gives , which is a Hamiltonian - path of . Thus is matching-fault-tolerant Hamiltonian-connected.
As an immediate consequence, the result also applies to the maximum-cardinality case in which the faulty set is a perfect matching.
Corollary 12. Let be a perfect matching of , where and . Then is Hamiltonian-connected.
Vertex-fault-tolerant Hamiltonian connectivity of
In this section, we investigate the Hamiltonian connectivity of Johnson graphs under vertex faults. Unlike an edge fault, which removes a single communication link, a vertex fault removes a vertex together with all of its incident edges and may therefore cause more extensive structural disruption.
For example, an exhaustive verification shows that the degree-based edge-fault bound cannot in general be carried over to vertex faults. In , deleting the six vertices
yields a subgraph containing no Hamiltonian path from to . We therefore seek a vertex-fault tolerance guarantee for Johnson graphs in this section.
The following lemma characterizes the intersection of the cross-layer neighborhoods of two vertices in .
Lemma 13. For any two distinct vertices , we have and
Proof. Since and are vertices in , they both contain the element . By definition, replacing the element in (or ) with any element not currently in the set yields a neighbor in . Thus, . We now determine the size of their common neighborhood based on their adjacency in .
Case 1. and are adjacent. Without loss of generality, let and , where . To find a common neighbor in , we must replace the element in both sets such that the resulting sets are identical. The only way to achieve this is to replace in with , and replace in with . Thus, their unique common neighbor in is exactly . Hence, .
Case 2. and are non-adjacent. Without loss of generality, let and , where . For any vertex , must not contain (since ), which means must be replaced by some element not in . Consequently, will still contain both and . However, lacks both and . A neighbor of in can acquire at most one of them (by replacing ). Therefore, no vertex in can contain both and , which implies . Thus, .
For the small base cases, we use exhaustive computational verification, which yields the following lemma.
Lemma 14. and are 3-vertex-fault-tolerant Hamiltonian-connected.
With the foundational base cases established, we now present the main theorem regarding the vertex-fault-tolerant Hamiltonian connectivity of .
Theorem 15. is -vertex-fault-tolerant Hamiltonian-connected whenever and .
Proof. We proceed by induction on . Since , the complete graph is trivially -vertex-fault-tolerant Hamiltonian-connected. For the base cases , and are 3-vertex-fault-tolerant Hamiltonian-connected by Lemma 14. Since , we may assume that .
For the inductive step, assume that and . The strong induction hypothesis asserts that is -vertex-fault-tolerant Hamiltonian-connected for any and . Let be a set of faulty vertices in with .
Consider two distinct arbitrary vertices and in . Since , there exists an element such that and . We partition along , yielding and , with and . Let and denote the restriction of on and , respectively. We consider two subcases based on the fault distribution.
Case 1. and . We first select candidate endpoints in to cross into . The number of available fault-free vertices in other than is . If we can choose two distinct candidates , then by Lemma 13, the cardinality of the neighborhood of in satisfies:
Since , we have . Thus, there exists at least one fault-free cross edge to . Note that we can always find two such candidates unless and . In this extreme scenario, only one candidate remains in , but consequently . The single candidate has neighbors in , which is greater than , ensuring a fault-free cross edge.
Without loss of generality, let be a fault-free neighbor of . By the induction hypothesis, there exists a Hamiltonian path in , and a Hamiltonian path in . Concatenating them via the edge yields a Hamiltonian path in .
Case 2. or . We only consider as the case can be handled symmetrically. Let be a faulty vertex in . Then, the remaining faults satisfy .
By the induction hypothesis, there exists a Hamiltonian path from to in , denoted by , where is the immediate neighbor of . Since is faulty, we truncate it to obtain a fault-free path segment in . Because , the vertex has neighbors in . Thus, we can choose a neighbor such that . By the induction hypothesis on , there exists a Hamiltonian path in . Connecting the two segments via the cross edge , the path is a fault-free Hamiltonian path joining and in .
Fault-Tolerant Algorithm and Complexity Analysis
In this section, we establish efficient algorithms based on the constructive proofs presented previously. The constructive logic for handling general edge faults, matching faults, and vertex faults shares a fundamental divide-and-conquer architecture based on the subgraph partitioning of . We first present the framework for general edge faults, which incorporates a dynamic partition selection subroutine. Subsequently, we introduce a unified routing algorithm for matching and vertex faults. Finally, we rigorously analyze the complexity of the proposed algorithms.
Routing under General Edge Faults
Throughout this section, every recursive instance is normalized using the complement isomorphism
Specifically, whenever , each vertex is replaced by its complement in , the parameter is replaced by , and the terminals and fault set are transformed accordingly. The routing algorithm is then applied to the normalized instance, and the resulting path is mapped back by the inverse complement transformation. Hence, every nontrivial recursive instance may be assumed to satisfy .
When the recursion reaches (or, equivalently, ), the problem reduces to Hamiltonian routing in a faulty complete graph. Let , where . For every pair of nonadjacent vertices in , we have and
Consequently,
Thus, satisfies the Ore-type sufficient condition for Hamiltonian connectivity. We use CompleteGraphRouting to denote the standard constructive procedure associated with this Ore-type condition. The faulty edges are processed successively. Whenever a faulty edge occurs on the current Hamiltonian path, the usual Ore-type path-rearrangement operation is applied to eliminate it while preserving the prescribed endpoints. Since at most faulty edges are processed and each path rearrangement requires at most a linear scan of the current path, a single invocation takes time.
Since and have small orders, all admissible fault configurations and terminal pairs can be precomputed exhaustively. We therefore treat SmallGraphRouting as a constant-time lookup routine.
Since has constant size, all exceptional configurations covered by Lemma 8 can be handled by a finite lookup table after canonical relabeling. We denote this constant-time procedure by SpecialJ63Routing in Algorithm 1. This approach guarantees that the base-case anomalies are resolved in time.
The structural correctness and termination of Algorithm 1 follow directly from the constructive proof of Theorem 7. We now analyze its complexity. Let denote the total number of vertices in .
Theorem 16. For , Algorithm 1 constructs a fault-free Hamiltonian path in asymptotically optimal time, where .
Proof. The total running time consists of path construction, partition selection, bridge selection, and the base-case routing procedures.
The recursive construction outputs each vertex exactly once. With linked path representations, concatenation of path segments requires constant time. Hence the pure path-construction cost is .
Let be the maximum recursion depth. At each recursive step, the first graph parameter decreases from to , and therefore
Algorithm 1: Hamiltonian Routing in $J(n,k)$ with General Edge Faults
Input: Graph parameters $n$, $k$; Terminals $u$, $v$; Fault set $F$ with $|F| \leq k(n-k)-3$
Output: A fault-free Hamiltonian path $P$ joining $u$ and $v$
Function RoutingGenEdge($n,k,u,v,F$):
if $k > n/2$ then
Transform $(u,v,F)$ to the complementary instance $(\bar{u},\bar{v},\bar{F})$ of
$J(n,n-k)$;
$\bar{P} \leftarrow$ RoutingGenEdge($n,n-k,\bar{u},\bar{v},\bar{F}$);
return the inverse-complement image of $\bar{P}$;
if $k = 1$ then return CompleteGraphRouting($n,u,v,F$);
if $(n,k) = (4,2)$ or $(n,k) = (5,2)$ then
return SmallGraphRouting($n,k,u,v,F$);
if The exceptional configuration of $J(6,3)$ in Lemma 8 occurs then
return SpecialJ63Routing($u,v,F$);
$i \leftarrow$ PartitionSelection($n,k,F$);
Partition into $X(i) \cong J(n-1,k-1)$ and $Y(i) \cong J(n-1,k)$;
if $u \in X(i)$ and $v \in Y(i)$ then
Select $a \in X(i)$ and $a' \in Y(i)$ such that $aa' \notin F$;
$P_1 \leftarrow$ RoutingGenEdge($n-1,k-1,u,a,F_X$);
$P_2 \leftarrow$ RoutingGenEdge($n-1,k,a',v,F_Y$);
return $P_1 \circ aa' \circ P_2$;
else if $u \in Y(i)$ and $v \in X(i)$ then
Select $a \in Y(i)$ and $a' \in X(i)$ such that $aa' \notin F$;
$P_1 \leftarrow$ RoutingGenEdge($n-1,k,u,a,F_Y$);
$P_2 \leftarrow$ RoutingGenEdge($n-1,k-1,a',v,F_X$);
return $P_1 \circ aa' \circ P_2$;
else if $u \in X(i)$ and $v \in X(i)$ then
$P_X \leftarrow$ RoutingGenEdge($n-1,k-1,u,v,F_X$);
Scan the edges of $P_X$ until an edge $x_1x_2$ admitting two distinct
fault-free cross-edges $x_1y_1$ and $x_2y_2$ is found;
Split $P_X$ at $(x_1,x_2)$ into $P_X^1$ (from $u$ to $x_1$) and $P_X^2$ (from $x_2$ to $v$);
$P_Y \leftarrow$ RoutingGenEdge($n-1,k,y_1,y_2,F_Y$);
return $P_X^1 \circ x_1y_1 \circ P_Y \circ y_2x_2 \circ P_X^2$;
else if $u \in Y(i)$ and $v \in Y(i)$ then
$P_Y \leftarrow$ RoutingGenEdge($n-1,k,u,v,F_Y$);
Select an edge $(y_1,y_2) \in E(P_Y)$ and two cross-edges $y_1x_1,y_2x_2 \notin F$;
Split $P_Y$ at $(y_1,y_2)$ into $P_Y^1$ (from $u$ to $y_1$) and $P_Y^2$ (from $y_2$ to $v$);
$P_X \leftarrow$ RoutingGenEdge($n-1,k-1,x_1,x_2,F_X$);
return $P_Y^1 \circ y_1x_1 \circ P_X \circ x_2y_2 \circ P_Y^2$;
Algorithm 2: PartitionSelection for General Edge Faults
Input: Parameters $n$, $k$; Faulty-edge set $F$
Output: An element $i \in [n]$ satisfying fault bounds for $X(i)$ and $Y(i)$
Function PartitionSelection($n$, $k$, $F$):
foreach $i \in [n]$ do
$C_X[i] \leftarrow 0$;
$C_Y[i] \leftarrow 0$;
foreach edge $e = (x,y) \in F$ do
foreach $i \in x \cap y$ do
$C_X[i] \leftarrow C_X[i] + 1$;
foreach $i \in [n] \setminus (x \cup y)$ do
$C_Y[i] \leftarrow C_Y[i] + 1$;
// Select the valid partition element
foreach $i \in [n]$ do
if $C_X[i] \leq (n-k)(k-1)-3$ and $C_Y[i] \leq (n-k-1)k-3$ then
return $i$;
return Error; // Unreachable by Theorem 7
For a fixed recursion depth , let be the set of recursive subproblems at that depth. The corresponding subgraphs are vertex-disjoint, and hence their internal faulty-edge sets are disjoint. Therefore,
For each faulty edge , Algorithm 2 (updating the counters) needs time. Thus the aggregate partition-selection cost at one recursion depth is
Summing over all recursion levels gives
Since
we obtain
For ,
and hence
The search for the required fault-free cross-layer edges is carried out along the recursively constructed paths, and its cost is included in the overall path-processing overhead.
It remains to consider the base cases. For a complete-graph leaf , let denote its internal faulty-edge set. A call to CompleteGraphRouting on requires time. Since these complete-graph leaves are vertex-disjoint,
Moreover, for every complete-graph leaf. Hence,
The fixed-size routines SmallGraphRouting and SpecialJ63Routing contribute only aggregate time. Combining all components,
Since explicitly outputting a Hamiltonian path containing all vertices requires time, we conclude that
Thus, Algorithm 1 is asymptotically optimal.
The boundary cases and require separate consideration. For both cases, the admissible number of general edge faults is linear in . Since the recursion depth is , the above partition-selection analysis gives an aggregate overhead of . For , we have
and hence the partition-selection overhead remains . For , however,
so the same analysis yields the conservative bound
Thus, under the direct implementation of Algorithm 2, the present analysis does not establish a linear-in- worst-case bound for . A more specialized or incrementally maintained partition-selection scheme may further reduce this overhead.
Algorithm 3: Fault-Tolerant Hamiltonian Path for Matching/Vertex Faults
Input: Graph parameters $n$, $k$; Terminals $u$, $v$; Fault set $F$;
FaultType $\in \{\mathrm{Matching}, \mathrm{Vertex}\}$
Output: A fault-free Hamiltonian path $P$ joining $u$ and $v$ in $J(n,k)-F$
Function RoutingMatchVertex($n$, $k$, $u$, $v$, $F$, FaultType):
if $k > n/2$ then
Transform $(u,v,F)$ into the complementary instance $(\bar{u},\bar{v},\bar{F})$ of
$J(n,n-k)$;
$\bar{P} \leftarrow$ RoutingMatchVertex($n,n-k,\bar{u},\bar{v},\bar{F}$, FaultType);
return the inverse-complement image of $\bar{P}$;
if $k=1$ then
return CompleteGraphRouting($n,u,v,F$, FaultType);
if $n=5$ then
return LookupBaseSmallGraphs($k,u,v,F$, FaultType);
Select an arbitrary element $i \in u \setminus v$;
Partition into $X(i) \cong J(n-1,k-1)$ and $Y(i) \cong J(n-1,k)$ with
$u \in X(i)$, $v \in Y(i)$;
$F_X \leftarrow F \cap X(i)$, $F_Y \leftarrow F \cap Y(i)$;
$(a,a') \leftarrow$ FindBridge($X(i),Y(i),u,v,F_X,F_Y$, FaultType, $F$);
$P_1 \leftarrow$ RoutingMatchVertex($n-1,k-1,u,a,F_X$, FaultType);
$P_2 \leftarrow$ RoutingMatchVertex($n-1,k,a',v,F_Y$, FaultType);
return $P_1 \circ aa' \circ P_2$;
Routing under Matching and Vertex Faults
We now establish the complexity of the unified routing algorithm for matching and vertex faults. To achieve asymptotic optimality, we assume that the fault set is pre-processed into a hash-based data structure, enabling average-time complexity for fault-membership queries (i.e., verifying if a vertex or edge is faulty).
Theorem 17. Algorithm 3 constructs a fault-free Hamiltonian path in asymptotically optimal time.
Proof. The total time complexity of the algorithm is determined by the recursive combinatorial path generation and the local overhead associated with the FindBridge subroutine at each recursion step.
Let denote the time required to construct the Hamiltonian path in . Thus, the recurrence relation can be formulated as:
Algorithm 4: Bridge Selection for Matching and Vertex Faults
Input: Subgraphs , ; Terminals , ; Fault sets , ; FaultType; Global fault set
Output: A valid fault-free cross-edge bridging and
Function FindBridge:
if FaultType == Matching then
Select an arbitrary candidate ;
foreach do
if then
return ;
else if FaultType == Vertex then
if and then
Select a set with size ;
foreach do
Select two distinct vertices ;
if then return ;
else
return
else
if then any node in ;
else any node in ;
Select a fault-free neighbor ;
Select a fault-free neighbor ;
return ; // Return a fault-free bridge
where is the time complexity of selecting a valid fault-free cross-edge.
Instead of exhaustively scanning the cross-neighbors for a selected candidate , we exploit the structural constraints of the fault models to achieve bridge selection:
Under matching faults: Since the fault set is a matching, at most one faulty edge is incident to any vertex . Therefore, the algorithm only generates at most two candidate cross-neighbors via elementary set operations (e.g., ) and test them using queries.
Under vertex faults: Whether selecting an arbitrary pair (when faults are distributed) or arbitrarily picking an fault node in (when ), the initial selections require no heuristic search and execute in strict time.
To locate the required intermediate fault-free neighbor, the algorithm utilizes hash queries in total.
Consequently, . The recurrence relation thus simplifies to:
Notice that the size of the graph precisely follows Pascal’s identity:
By induction, solving this recurrence yields . Furthermore, any algorithm that constructs and outputs a Hamiltonian path must sequentially visit and output all vertices, which requires at least time. Combining the upper and lower bounds, we conclude that the total time complexity is , proving that the algorithm is asymptotically optimal.
Simulation and Performance Evaluation
To evaluate the computational efficiency of the proposed routing algorithms, we measure the Average Execution Time (AET) required to construct a fault-free Hamiltonian path. The experiments are conducted on for . For each network size and fault model, one fault configuration at the maximum cardinality guaranteed by the corresponding theoretical result is generated and fixed across 100 randomly selected source-destination pairs. The timing interval includes only the execution of the routing algorithm and excludes graph construction, fault generation, terminal-pair sampling, and post-routing correctness verification. All experiments were implemented in Python 3.7 and executed on a machine equipped with an Intel(R) Core(TM) i7-8550U processor and 8 GB of RAM running Windows 10. All reported routing times were measured using a single thread.
Figure 2 reports the AET of the three fault-tolerant Hamiltonian routing algorithms for , , corresponding to network sizes ranging from to . The fault configurations contain general faulty edges, a faulty-edge set forming a perfect matching, and faulty vertices for the general-edge, matching, and vertex fault models, respectively. For every tested network size and fault model, all 100 routing trials successfully produced valid fault-free Hamiltonian paths.

Figure 2. Average execution time (AET) versus network size for the proposed Hamiltonian routing algorithms under general edge, matching, and vertex faults in , . Each data point is averaged over 100 randomly selected source-destination pairs at the maximum fault cardinality guaranteed by the corresponding fault-tolerance result.
As shown in Figure 2, the execution times of all three algorithms increase smoothly with the network size and exhibit an approximately linear growth trend over the tested range. As increases from 120 to 12,870, the AET increases from to s under general edge faults, from to s under matching faults, and from to s under vertex faults. Linear regressions of AET against yield coefficients of determination of 0.9990, 0.9978, and 0.9982 for the general-edge, matching, and vertex fault models, respectively. These high goodness-of-fit values indicate that the measured runtime is well approximated by a linear function of over the tested range, supporting the theoretical scalability analysis developed in the preceding subsection.
The three curves remain relatively close to one another across all tested network scales, indicating comparable practical efficiency under the different fault models. The vertex-fault algorithm consistently exhibits the lowest AET, reaching approximately 0.274 s for , whereas the general-edge and matching algorithms require approximately 0.300 and 0.318 s, respectively. Despite these modest implementation-level differences, no qualitatively different growth behavior is observed among the three fault models. It is also noteworthy that the matching-fault experiment for contains a perfect matching of 6,435 faulty edges, compared with only 61 arbitrary faulty edges under the general-edge model. Thus, although the matching-fault model permits a substantially larger number of faulty edges because of its structural restriction, its routing time remains comparable to that under general edge faults.
Since the algorithms were implemented in Python, the absolute execution times are implementation dependent; nevertheless, the observed growth trend agrees well with the theoretical scalability analysis.
Conclusion
In this paper, we have investigated the fault-tolerant Hamiltonian connectivity of the Johnson graph , a highly symmetric graph with potential as a topology for multiprocessor systems. We first established that is -edge-fault-tolerant Hamiltonian-connected, which attains the natural degree-based upper bound. Second, to reflect practical engineering scenarios where faulty links do not cluster, we proved that remains Hamiltonian-connected under any matching fault for . Finally, addressing the destructive nature of node failures, we demonstrated that is -vertex-fault-tolerant Hamiltonian-connected.
When comparing the Johnson network with bipartite multiprocessor topologies such as the hypercube and the star graph , a fundamental topological distinction emerges. For bipartite interconnection networks, Hamiltonian laceability serves as the natural counterpart of Hamiltonian connectivity, since the bipartition prevents Hamiltonian paths from joining arbitrary pairs of vertices. Consequently, a spanning linear array can generally be embedded only between endpoints in opposite partite sets. This parity restriction limits endpoint flexibility when arbitrary processors are required to serve as the two ends of a spanning linear structure. In contrast, guarantees a Hamiltonian path between any two fault-free vertices, even under the fault conditions considered in this paper. This unrestricted endpoint flexibility, together with its strong fault-tolerance highlights the potential of Johnson graphs as robust interconnection topologies.
While this work establishes the tight bound for general edge faults and matching faults, the optimal upper bound for the vertex-fault tolerance of is yet to be determined. As demonstrated by our exhaustive computer search on , the degree-minus-three edge-fault bound does not extend to vertex faults. Therefore, determining the exact, tight upper bound for the vertex-fault-tolerant Hamiltonian connectivity of general Johnson graphs remains a challenging problem. Additionally, investigating conditional edge-fault models under the minimum-degree constraint is another natural direction for further characterizing the fault-tolerant Hamiltonian connectivity of Johnson graphs.
Data Availability Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
Declarations
Competing Interests The authors have not disclosed any competing interests.
References
- [1]C. Godsill and G. Royle, Algebraic Graph Theory. New York: Springer, 2001.
- [2]A. E. Brouwer, S. M. Cioabă, F. Ihringer, and M. McGinnis, “The smallest eigenvalues of hamming graphs, johnson graphs and other distance-regular graphs with classical parameters,” Journal of Combinatorial Theory, Series B, vol. 133, pp. 88–121, 2018.arxiv.org/abs/1709.09011
- [3]M. Koshelev, “New lower bound on the modularity of johnson graphs,” Moscow Journal of Combinatorics and Number Theory, vol. 10, no. 1, pp. 77–82, 2021.DOI
- [4]——, “Spectrum of johnson graphs,” Discrete Mathematics, vol. 346, no. 3, p. 113262, 2023.DOI
- [5]B. Alspach, “Hamilton paths in cayley graphs on coxeter groups: I,” Ars Mathematica Contemporanea, vol. 8, pp. 35–53, 2015.DOI
- [6]V. S. Kozhevnikov, A. M. Raigorodskii, and M. E. Zhukovskii, “Large cycles in random generalized johnson graphs,” Discrete Mathematics, vol. 345, no. 3, p. 112721, 2022.arxiv.org/abs/2012.07314
- [7]J. Liu and H. Lü, “Paired many-to-many 2-disjoint path cover of johnson graphs,” 2025, arXiv:2507.15463.arxiv.org/abs/2507.15463
- [8]J.-H. Park, “On paired 2-disjoint path coverability of johnson and generalized johnson graphs,” IEEE Access, vol. 14, pp. 42366–42380, 2026.DOI
- [9]M. Besta, J. Domke, M. Schneider, M. Konieczny, S. D. Girolamo, T. Schneider, A. Singla, and T. Hoefler, “High-performance routing with multipathing and path diversity in ethernet and hpc networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 4, pp. 943–959, 2021.arxiv.org/abs/2007.03776
- [10]M. Ebrahimi, M. Daneshtalab, P. Liljeberg, J. Plosila, J. Flich, and H. Tenhunen, “Path-based partitioning methods for 3d networks-on-chip with minimal adaptive routing,” IEEE Transactions on Computers, vol. 63, no. 3, pp. 718–733, 2014.
- [11]L.-C. Ye and J.-R. Liang, “Five-round adaptive diagnosis in hamiltonian networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 9, pp. 2459–2464, 2015.DOI
- [12]Q. Dong, J. Zhou, Y. Fu, and H. Gao, “Hamiltonian connectivity of restricted hypercube-like networks under the conditional fault model,” Theoretical Computer Science, vol. 472, pp. 46–59, 2013.DOI
- [13]H. Guo, R.-X. Hao, and J.-M. Chang, “2-edge-hamilton-connectedness of complete hypercube-like networks,” Discrete Applied Mathematics, vol. 381, pp. 23–31, 2026.DOI
- [14]S.-Y. Hsieh and C.-N. Kuo, “Hamiltonian-connectivity and strongly hamiltonian-laceability of folded hypercubes,” Computers & Mathematics with Applications, vol. 53, pp. 1040–1044, 2007.DOI
- [15]C.-H. Huang and J.-F. Fang, “The pancyclicity and the hamiltonian-connectivity of the generalized base-b hypercube,” Computers & Electrical Engineering, vol. 34, pp. 263–269, 2008.DOI
- [16]C.-D. Park and K.-Y. Chwa, “Hamiltonian properties on the class of hypercube-like networks,” Information Processing Letters, vol. 91, pp. 11–17, 2004.DOI
- [17]H.-C. Hsu, Y.-L. Hsieh, J. J. M. Tan, and L.-H. Hsu, “Fault hamiltonicity and fault hamiltonian connectivity of the (n, k)-star graphs,” Networks, vol. 42, pp. 189–201, 2003.DOI
- [18]H.-C. Hsu, T.-K. Li, J. J. M. Tan, and L.-H. Hsu, “Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs,” IEEE Transactions on Computers, vol. 53, no. 1, pp. 39–53, 2004.DOI
- [19]T.-L. Kueng, C.-K. Lin, T. Liang, J. J. M. Tan, and L.-H. Hsu, “Fault-tolerant hamiltonian connectedness of cycle composition networks,” Applied Mathematics and Computation, vol. 196, pp. 245–256, 2008.DOI
- [20]B. Alspach, “Johnson graphs are hamilton-connected,” Ars Mathematica Contemporanea, vol. 6, pp. 21–23, 2013.DOI
- [21]R.-X. Hao, R. Zhang, Y.-Q. Feng, and J.-X. Zhou, “Hamiltonian cycle embedding for fault tolerance in balanced hypercubes,” Applied Mathematics and Computation, vol. 244, pp. 447–456, 2014.DOI
- [22]T. Lan and H. Lü, “Hamiltonian cycles of balanced hypercube with more faulty edges,” Theoretical Computer Science, vol. 947, p. 113708, 2023.DOI
- [23]P. Li and M. Xu, “Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes,” Applied Mathematics and Computation, vol. 307, pp. 180–192, 2017.arxiv.org/abs/1606.05152
- [24]C.-H. Tsai, J. J. M. Tan, T. Liang, and L.-H. Hsu, “Fault-tolerant hamiltonian laceability of hypercubes,” Information Processing Letters, vol. 83, pp. 301–306, 2002.DOI
- [25]Q. Zhou, D. Chen, and H. Lü, “Fault-tolerant hamiltonian laceability of balanced hypercubes,” Information Sciences, vol. 300, pp. 20–27, 2015.DOI
- [26]T.-Y. Ho, Y.-K. Shih, J.-M. Tan, and L.-H. Hsu, “Conditional fault hamiltonian connectivity of the complete graph,” Information Processing Letters, vol. 109, pp. 585–588, 2009.DOI
- [27]S.-Y. Hsieh, C.-W. Lee, and C.-H. Huang, “Conditional edge-fault hamiltonian-connectivity of restricted hypercube-like networks,” Information and Computation, vol. 251, pp. 314–334, 2016.
- [28]H. Zhuang, X.-Y. Li, J.-M. Chang, and D. Wang, “An efficient algorithm for hamiltonian path embedding of k-ary n-cubes under the partitioned edge fault model,” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 6, pp. 1802–1815, 2023.DOI
- [29]Y. Wang, J. Zai, Z. Liu, J. Chen, and E. Sabir, “Hamiltonian connectivity in k-ary n-cubes under a region-based fault model,” Information Sciences, vol. 755, p. 123811, 2026.DOI
- [30]D. Dimitrov, T. Dvořák, P. Gregor, and R. Škrekovski, “Gray codes avoiding matchings,” Discrete Mathematics & Theoretical Computer Science, vol. 11, pp. 123–148, 2009.DOI
- [31]J. Dybizbański and A. Szepietowski, “Hamiltonian cycles and paths in hypercubes with disjoint faulty edges,” Information Processing Letters, vol. 172, p. 106157, 2021.DOI
- [32]T. Lan and H. Lü, “Hamiltonian cycles of balanced hypercube with disjoint faulty edges,” Information Processing Letters, vol. 187, p. 106518, 2025.
- [33]W. Zuo and H. Lü, “Hamiltonian cycle and path of folded hypercube with faulty matchings,” Discrete Applied Mathematics, vol. 381, pp. 71–79, 2026.DOI
- [34]H. Liu and Y. Tian, “Fault hamiltonicity and fault hamiltonian connectivity of (n, k)-bubble sort graphs,” Applied Mathematics and Computation, vol. 531, p. 130218, 2026.DOI
- [35]M. Abdallah and E. Cheng, “Fault-tolerant hamiltonian connectivity of 2-tree-generated networks,” Theoretical Computer Science, vol. 907, pp. 62–81, 2022.DOI
- [36]S.-Y. Hsieh, “Some edge-fault-tolerant properties of the folded hypercube,” Networks, vol. 51, no. 2, pp. 92–101, 2008.
- [37]T.-K. Li and J. J. M. Tan, “Hamiltonian laceability on edge fault star graph,” in Proceedings of the 9th International Conference on Parallel and Distributed Systems, 2002.DOI
- [38]I. A. Stewart and Y. Xiang, “Embedding long paths in k-ary n-cubes with faulty nodes and links,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 8, pp. 1071–1085, 2008.DOI
