betaFeedback

WorksComputer Science

Fault-tolerant Hamiltonian connectivity of Johnson graphs

Abstract

Johnson graphs J(n,k)J(n,k) 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 J(n,k)J(n,k) remains Hamiltonian-connected after the deletion of any set of at most k(n−k)−3k(n-k)-3 edges for n≥4n\geq4. Since J(n,k)J(n,k) is k(n−k)k(n-k)-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 J(n,k)J(n,k) remains Hamiltonian-connected after the deletion of an arbitrary matching for n≥5n\geq5, including a perfect matching whenever one exists. For vertex failures, we prove that J(n,k)J(n,k) is (n−2)(n-2)-vertex-fault-tolerant Hamiltonian-connected for n≥5n\geq5. All three results are constructive and lead to recursive fault-tolerant Hamiltonian routing algorithms. Simulation results on Johnson graphs with up to 12,87012{,}870 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 nn and kk with 1≤k<n1 \le k < n, the Johnson graph J(n,k)J(n,k) has all kk-subsets of [n]={1,2,…,n}[n] = \{1,2,\ldots,n\} as its vertices, where two vertices are adjacent whenever their intersection has size k−1k-1. Thus, J(n,k)J(n,k) has (nk)\binom{n}{k} vertices and is k(n−k)k(n-k)-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], (n,k)(n,k)-star graphs [17], arrangement graphs [18], and cycle composition networks [19]. For Johnson graphs, Alspach [20] proved that J(n,k)J(n,k) 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 n≥4n \ge4, QnQ_n is Hamiltonian if and only if every dimension contains two fault-free crossing edges of different parity. For the balanced hypercube BHnBH_n, 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 FF of the folded hypercube FQnFQ_n, FQn−FFQ_n-F remains Hamiltonian for n≥2n \ge2 and is Hamiltonian laceable for every odd n≥3n \ge3. In particular, in both BHnBH_n and FQnFQ_n, the number of admissible faulty edges can reach 22n−12^{2n-1} and 2n−12^{n-1}, respectively, both exponential in the network dimension nn.

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 (n,k)(n,k)-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.

NetworkBipartiteHamiltonian PropertyFault ModelFault-Tolerance Result
Hypercube QnQ_nYesHamiltonian Laceability<br>HamiltonicityGeneral Edge<br>Matchingn−2n-2 [24]<br>Dimension-parity condition [31]
Balanced Hypercube BHnBH_nYesHamiltonian Laceability<br>HamiltonicityGeneral Edge<br>Matching2n−22n-2 [25]<br>general matching [32]
Folded Hypercube FQnFQ_n (odd nn)YesStrongly Hamiltonian Laceability<br>Hamiltonian LaceabilityGeneral Edge<br>Matchingn−1n-1 [36]<br>Arbitrary matching [33]
Star Graph SnS_nYesHamiltonian LaceabilityGeneral Edgen−3n-3 [37]
kk-ary nn-cube (k≥4k \ge4 even)YesHamiltonian LaceabilityGeneral Edge2n−22n-2 [38]
(n,k)(n,k)-Star Graph Sn,kS_{n,k} (n−k≥2n-k \ge2)NoHamiltonian ConnectivityMixed Vertex/Edge∣Fv∣+∣Fe∣≤n−4\lvert F_v\rvert+\lvert F_e\rvert\le n-4 [17]
Arrangement Graph An,kA_{n,k}NoHamiltonian ConnectivityMixed Vertex/Edge∣Fv∣+∣Fe∣≤k(n−k)−3\lvert F_v\rvert+\lvert F_e\rvert\le k(n-k)-3 [18]
(n,k)(n,k)-Bubble Sort GraphNoHamiltonian ConnectivityMixed Vertex/Edge∣Fv∣+∣Fe∣≤n−4\lvert F_v\rvert+\lvert F_e\rvert\le n-4 [34]
2-tree-generated networkNoHamiltonian ConnectivityMixed Vertex/Edge∣Fv∣+∣Fe∣≤2n−7\lvert F_v\rvert+\lvert F_e\rvert\le2n-7 [35]
Johnson J(n,k)J(n,k)NoHamiltonian ConnectivityGeneral Edge<br>Matching<br>Vertexk(n−k)−3k(n-k)-3<br>Arbitrary matching<br>n−2n-2

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 J(n,k)J(n,k) 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 J(n,k)−FJ(n,k)-F remains Hamiltonian-connected for every edge-fault set FF satisfying ∣F∣≤k(n−k)−3|F| \le k(n-k)-3. Since J(n,k)J(n,k)

Note: FvF_v and FeF_e denote the sets of faulty vertices and faulty edges, respectively.

is k(n−k)k(n-k)-regular, this bound reaches the natural upper bound imposed by the minimum-degree obstruction.

  • Matching faults. We establish that J(n,k)J(n,k) 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 12(nk)\frac{1}{2}\binom{n}{k}, i.e., half the order of J(n,k)J(n,k).

  • Vertex faults. We show that J(n,k)J(n,k) is (n−2)(n-2)-vertex-fault-tolerant Hamiltonian-connected; that is, after the removal of any set of at most n−2n-2 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 J(n,k)J(n,k)

We first introduce some notation and preliminary results that will be used throughout this paper. For a fixed element i∈[n]i \in[n], let X(i)X(i) denote the subgraph of J(n,k)J(n,k) induced by the vertices containing ii, and let Y(i)Y(i) denote the subgraph induced by the vertices not containing ii. When the choice of ii is clear from the context, we simply write XX and YY. Clearly, X≅J(n−1,k−1)X \cong J(n-1,k-1) and Y≅J(n−1,k)Y \cong J(n-1,k). For an edge-fault set F⊆E(J(n,k))F \subseteq E(J(n,k)), let FXF_X and FYF_Y denote the sets of faulty edges contained in XX and YY, respectively. We also recall that J(n,k)≅J(n,n−k)J(n,k) \cong J(n,n-k) for 0≤k≤n0 \leq k \leq n, and J(n,1)≅KnJ(n,1) \cong K_n.

Lemma 1. [20] For 0≤k≤n0 \leq k \leq n and n≥1n \geq1, J(n,k)J(n,k) is Hamiltonian-connected.

Lemma 2. [7] J(n,k)J(n,k), for n≥4n \geq4 and 1≤k≤n−11 \leq k \leq n-1, is paired 2-coverable.

Lemma 3. [26] Let F⊆E(Kn)F \subseteq E(K_n) satisfy δ(Kn−F)≥3\delta(K_n-F) \geq3. Then Kn−FK_n-F is Hamiltonian-connected whenever ∣F∣≤2n−10|F| \leq2n-10 for n∉{4,5,8,10}n \notin\{4,5,8,10\}; the corresponding maximum bounds for n=4,5,8,10n=4,5,8,10 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 n≥4n \geq4, KnK_n is (n−4)(n-4)-edge-fault-tolerant Hamiltonian-connected.

Proof. Let F⊆E(Kn)F \subseteq E(K_n) be any faulty edge set with ∣F∣≤n−4|F| \leq n-4. Since every vertex of KnK_n has degree n−1n-1,

δ(Kn−F)≥(n−1)−∣F∣≥(n−1)−(n−4)=3.\delta(K_n-F) \geq(n-1)-|F| \geq(n-1)-(n-4)=3.

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 n≥6n \geq6 and n∉{8,10}n \notin\{8,10\}, then ∣F∣≤n−4≤2n−10|F| \leq n-4 \leq2n-10. For the exceptional cases n∈{4,5,8,10}n \in\{4,5,8,10\}, we have ∣F∣≤0,1,4,6|F| \leq0,1,4,6, respectively, which do not exceed the corresponding bounds 0, 2, 5, 9 given in Lemma 3. Therefore, Kn−FK_n-F 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 FF, we enumerate all pairs of distinct vertices u,v∈V(J(n,k)−F)u,v \in V(J(n,k)-F) and exhaustively verify the existence of a Hamiltonian uu-vv path in J(n,k)−FJ(n,k)-F.

Lemma 5. J(4,2)J(4,2) is 1-edge-fault-tolerant Hamiltonian-connected.

Since J(5,2)≅J(5,3)J(5,2) \cong J(5,3), by computationally verifying J(5,2)J(5,2), we immediately obtain the following lemma.

Lemma 6. Both J(5,2)J(5,2) and J(5,3)J(5,3) 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 GG be a graph with minimum degree δ\delta. If δ−2\delta-2 edges incident with a vertex xx fail, then xx has only two fault-free neighbors, say uu and vv. Any Hamiltonian path joining uu and vv would necessarily contain the subpath ⟨u,x,v⟩\langle u,x,v\rangle, preventing the path from spanning the remaining vertices. Hence, the ordinary edge-fault Hamiltonian-connectivity bound of GG cannot exceed δ−3\delta-3. Since J(n,k)J(n,k) is k(n−k)k(n-k)-regular, its edge-fault Hamiltonian-connectivity bound is at most k(n−k)−3k(n-k)-3. We next show that this upper bound is attained by Johnson graphs.

Theorem 7. For n≥4n \ge4, 1≤k≤n−11 \le k \le n-1, J(n,k)J(n,k) is (k(n−k)−3)(k(n-k)-3)-edge-fault-tolerant Hamiltonian-connected.

Proof. Let FF be a set of faulty edges in J(n,k)J(n,k) satisfying ∣F∣≤(n−k)k−3|F| \le(n-k)k-3. It follows from Corollary 4, and Lemmas 5 and 6, that the statement holds for J(n,1)J(n,1), J(n,n−1)J(n,n-1) with n≥4n \ge4, and for J(4,2)J(4,2), J(5,2)J(5,2) and J(5,3)J(5,3).

When considering J(n,k)J(n,k) with n≥6n \ge6 and 2≤k≤n−22 \le k \le n-2, the induction hypotheses are: J(m,k′)J(m,k') is ((m−k′)k′−3)((m-k')k'-3)-edge-fault-tolerant Hamiltonian-connected whenever 1<k′<k1 < k' < k and m>k′m > k', or J(m,k)J(m,k) is ((m−k)k−3)((m-k)k-3)-edge-fault-tolerant Hamiltonian-connected whenever m<nm < n and k<mk < m.

Case 1. n<2kn < 2k. Then n−k<kn-k < k. Since J(n,k)≅J(n,n−k)J(n,k) \cong J(n,n-k), the induction hypothesis applied to J(n,n−k)J(n,n-k) yields that J(n,n−k)J(n,n-k) is ((n−k)k−3)((n-k)k-3)-edge-fault-tolerant Hamiltonian-connected. Hence, J(n,k)J(n,k) has the same property.

Case 2. n≥2kn \ge2k. Let

A={i∈[n]:∣FX(i)∣≥(n−k)(k−1)−2}.A=\left\{i\in[n]:|F_{X(i)}|\ge(n-k)(k-1)-2\right\}.

We claim that ∣A∣≤k|A| \le k. Suppose on the contrary that ∣A∣≥k+1|A| \ge k+1. Then

∑i∈A∣FX(i)∣≥[(n−k)(k−1)−2](k+1).\sum_{i\in A}|F_{X(i)}|\ge\left[(n-k)(k-1)-2\right](k+1).

Since the two endpoints of each edge share k−1k-1 common elements, the sum ∑i∈A∣FX(i)∣\sum_{i\in A}|F_X(i)| counts each edge at most k−1k-1 times. Thus,

∣F∣≥1k−1∑i∈A∣FX(i)∣≥[(n−k)(k−1)−2]k+1k−1=(n−k)k+n−(k−1+4k−1+3).\begin{aligned} |F| \ge\frac{1}{k-1}\sum_{i\in A}|F_X(i)| \\ &\ge[(n-k)(k-1)-2]\frac{k+1}{k-1} \\ &= (n-k)k+n-\left(k-1+\frac{4}{k-1}+3\right). \end{aligned}

Since 2≤k≤n22\le k\le\frac{n}{2}, we have

k−1+4k−1+3≤max⁡{8,n2+8n−2+2}.k-1+\frac{4}{k-1}+3\le\max\left\{8,\frac{n}{2}+\frac{8}{n-2}+2\right\}.

Note that n≥6n\ge6, so we have

∣F∣≥(n−k)k−2>(n−k)k−3.|F|\ge(n-k)k-2>(n-k)k-3.

Hence, the claim holds.

Given that ∣A∣≤k|A|\le k, define B=[n]∖AB=[n]\setminus A. Consequently, ∣B∣≥n−k|B|\ge n-k. Next, we demonstrate by contradiction that BB must contain at least one element jj such that ∣FY(j)∣≤(n−k−1)k−3|F_Y(j)|\le(n-k-1)k-3, except for the case where n=6n=6 and k=∣A∣=∣B∣=3k=|A|=|B|=3. Suppose no such jj exists in BB. Then,

∑j∈B∣FY(j)∣≥[(n−k−1)k−2]⋅∣B∣.\sum_{j\in B}|F_Y(j)|\ge[(n-k-1)k-2]\cdot|B|.

If an edge is contained in FY(j)F_Y(j), then the two endpoints of the edge do not contain jj. Since the union of the kk-sets corresponding to the endpoints of one edge contains k+1k+1 elements, the sum ∑j∈B∣FY(j)∣\sum_{j\in B}|F_Y(j)| counts each edge at most n−k−1n-k-1 times. Then

∣F∣≥1n−k−1∑j∈B∣FY(j)∣≥∣B∣n−k−1[(n−k−1)k−2]≥(n−k)k−2(n−k)n−k−1.\begin{aligned} |F|\ge\frac{1}{n-k-1}\sum_{j\in B}|F_Y(j)| \\ &\ge\frac{|B|}{n-k-1}[(n-k-1)k-2] \\ &\ge(n-k)k-\frac{2(n-k)}{n-k-1}. \end{aligned}

Note that 2≤k≤n22\le k\le\frac{n}{2} and n≥6n\ge6.

(1) If n≠6n\ne6 or k≠3k\ne3, we have n−k>3n-k>3, which implies 2(n−k)n−k−1<3\frac{2(n-k)}{n-k-1}<3. Thus,

∣F∣≥(n−k)k−2(n−k)n−k−1>(n−k)k−3,|F|\ge(n-k)k-\frac{2(n-k)}{n-k-1}>(n-k)k-3,

which contradicts the assumption that ∣F∣≤(n−k)k−3|F| \le(n-k)k-3.

(2) If n=6n=6 and k=3k=3, we have n−k=3n-k=3, which yields

∣F∣≥(n−k)k−2(n−k)n−k−1=(n−k)k−3.|F| \ge(n-k)k-\frac{2(n-k)}{n-k-1}=(n-k)k-3.

This implies that ∣F∣=6|F|=6 and ∣B∣≥n−k=3|B|\ge n-k=3. If ∣B∣>3|B|>3 (i.e., ∣B∣≥4|B|\ge4), then

∣F∣≥45−k[(5−k)k−2]=8>6,|F| \ge\frac{4}{5-k}[(5-k)k-2]=8>6,

which is impossible since ∣F∣≤6|F|\le6.

Therefore, except for the case n=6n=6 and k=∣A∣=∣B∣=3k=|A|=|B|=3, there exists an element j∈Bj\in B such that

∣FX(j)∣≤(n−k)(k−1)−3and∣FY(j)∣≤(n−k−1)k−3.|F_{X(j)}|\le(n-k)(k-1)-3 \qquad\text{and} \qquad|F_{Y(j)}|\le(n-k-1)k-3.

Fix such an element jj, and write X=X(j)X=X(j) and Y=Y(j)Y=Y(j) in what follows.

Let uu and vv be any two distinct vertices of J(n,k)J(n,k). We distinguish the following cases according to the locations of uu and vv in the induced subgraphs XX and YY. For the case n=6n=6 with k=∣A∣=∣B∣=3k=|A|=|B|=3, if there exists an element jj such that the faulty edge sets of the two induced subgraphs XX and YY determined by jj satisfy the above inequality, then the desired result follows directly by induction. Otherwise, Lemma 8 establishes that J(6,3)J(6,3) remains 6-edge-fault Hamiltonian-connected.

Case 2.1. u,v∈Xu,v\in X. By the induction hypothesis, there exists a Hamiltonian path joining uu and vv in X−FX-F, which we denote by ⟨u=x1,x2,…,xt−1,xt=v⟩\langle u=x_1,x_2,\ldots,x_{t-1},x_t=v\rangle, where t=(n−1k−1)t=\binom{n-1}{k-1}. For n≥6n\ge6 and n≥2k≥4n\ge2k\ge4, we have

⌊(n−1k−1)2⌋((n−k)−[(n−k)k−3])≥12(n−1k−1)(n−k)−12(n−k)−(n−k)k+3≥12[(n−1k−1)−2k−1](n−k)+3≥3.\begin{aligned} \left\lfloor\frac{\binom{n-1}{k-1}}{2}\right\rfloor\left((n-k)-[(n-k)k-3]\right) &\ge\frac{1}{2}\binom{n-1}{k-1}(n-k)-\frac{1}{2}(n-k)-(n-k)k+3\\ &\ge\frac{1}{2}\left[\binom{n-1}{k-1}-2k-1\right](n-k)+3\\ &\ge3. \end{aligned}

This implies that there exist two non-faulty edges xly′x_ly' and xl+1y′′x_{l+1}y'' such that y′,y′′∈V(Y)y',y''\in V(Y) and y′≠y′′y'\ne y''. By the induction hypothesis, there exists a Hamiltonian path joining y′y' and y′′y'' in Y−FY-F, denoted by ⟨y′,P1,y′′⟩\langle y',P_1,y''\rangle. Then ⟨u,…,xl,y′,P1,y′′,xl+1,…,v⟩\langle u,\ldots,x_l,y',P_1,y'',x_{l+1},\ldots,v\rangle is a Hamiltonian path joining uu and vv in J(n,k)−FJ(n,k)-F.

Case 2.2. u,v∈Yu,v\in Y. By the induction hypothesis, there exists a Hamiltonian path joining uu and vv in Y−FY-F, denoted by ⟨u=y1,y2,…,ys−1,ys=v⟩\langle u=y_1,y_2,\ldots,y_{s-1},y_s=v\rangle, where s=(n−1k)s=\binom{n-1}{k}. For n≥6n \ge6 and n≥2k≥4n \ge2k \ge4, we have

⌊(n−1k)2⌋k−[(n−k)k−3]≥12(n−1k)k−12k−(n−k)k+3≥12[(n−1k)−2n+2k−1]k+3≥3.\begin{aligned} \left\lfloor\frac{\binom{n-1}{k}}{2} \right\rfloor k - [(n-k)k-3] &\ge\frac{1}{2}\binom{n-1}{k}k-\frac{1}{2}k-(n-k)k+3\\ &\ge\frac{1}{2}\left[\binom{n-1}{k}-2n+2k-1\right]k+3\\ &\ge3. \end{aligned}

This implies that there exist two non-faulty edges x′ymx'y_m and x′′ym+1x''y_{m+1} such that x′,x′′∈V(X)x',x'' \in V(X) and x′≠x′′x' \ne x''. By the induction hypothesis, there exists a Hamiltonian path joining x′x' and x′′x'' in X−FX-F, denoted by ⟨x′,P2,x′′⟩\langle x',P_2,x''\rangle. Then ⟨u,…,ym,x′,P2,x′′,ym+1,…,v⟩\langle u,\ldots,y_m,x',P_2,x'',y_{m+1},\ldots,v\rangle is a Hamiltonian path joining uu and vv in J(n,k)−FJ(n,k)-F.

Case 2.3. u∈Xu \in X and v∈Yv \in Y. Let S={ab∈E(J(n,k)):a∈X∖{u},b∈Y∖{v}}S=\{ab \in E(J(n,k)):a \in X\setminus\{u\},b \in Y\setminus\{v\}\}. Then

∣S∣≥(n−1k−1)(n−k)−n>(n−k)k−3≥∣F∣.|S| \ge\binom{n-1}{k-1}(n-k)-n>(n-k)k-3\ge|F|.

This implies that there exists an edge ab∈S−Fab \in S-F. By the induction hypothesis, there exists a Hamiltonian path joining uu and aa (resp. vv and bb) in X−FX-F (resp. Y−FY-F), denoted by ⟨u,P3,a⟩\langle u,P_3,a\rangle (resp. ⟨b,P4,v⟩\langle b,P_4,v\rangle). Clearly, the path ⟨u,P3,a,b,P4,v⟩\langle u,P_3,a,b,P_4,v\rangle is a Hamiltonian path joining uu and vv in J(n,k)−FJ(n,k)-F.

In the following lemma, we deal with the exceptional case from Theorem 7.

Lemma 8. Let F⊆E(J(6,3))F \subseteq E(J(6,3)) with ∣F∣≤6|F| \le6, and define

A={i∈[6]:∣FX(i)∣≥4},B=[6]∖A.A=\{i \in[6]:|F_{X(i)}| \ge4\}, \qquad B=[6]\setminus A.

Suppose ∣A∣=∣B∣=3|A|=|B|=3 and ∣FY(j)∣≥4|F_{Y(j)}| \ge4 for every j∈Bj \in B. Then J(6,3)−FJ(6,3)-F is Hamiltonian-connected.

Proof. Since two adjacent vertices of J(6,3)J(6,3) share exactly two elements, each faulty edge is counted exactly twice in ∑i=16∣FX(i)∣\sum_{i=1}^{6}|F_{X(i)}|. Hence,

2∣F∣=∑i=16∣FX(i)∣≥∑i∈A∣FX(i)∣≥3⋅4=12.2|F|=\sum_{i=1}^{6}|F_{X(i)}|\ge\sum_{i\in A}|F_{X(i)}|\ge3\cdot4=12.

Since ∣F∣≤6|F| \le6, it follows that ∣F∣=6|F|=6. Moreover, equality holds throughout. Consequently,

∣FX(i)∣=4for every i∈A,|F_{X(i)}|=4 \qquad\text{for every } i \in A,

and no faulty edge is counted by FX(j)F_{X(j)} for any j∈Bj \in B. Thus, the two common elements of the endpoints of every faulty edge belong to AA. Without loss of generality, let A={1,2,3}A = \{1,2,3\} and B={4,5,6}B = \{4,5,6\}. For convenience, let CEtCE_t (t=1,2,⋯ ,6t = 1,2,\cdots,6) denote the set of elements common to the two endpoints of the tt-th faulty edge in FF. By the definition of AA, among the six sets CEtCE_t, 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 CEtCE_t is exactly 12, it follows that there are exactly two sets containing {1,2}\{1,2\}, exactly two sets containing {1,3}\{1,3\}, and exactly two sets containing {2,3}\{2,3\}. On the other hand, by the assumption, for any j∈Bj \in B, we have ∣FY(j)∣≥4|F_Y(j)| \ge4. Since jj cannot be a common element of the two endpoints of a faulty edge, each j∈Bj \in B can occur in at most two endpoints of faulty edges. Therefore, the number of endpoints containing elements from {4,5,6}\{4,5,6\} is at most six. Consequently, at least six endpoints correspond to vertices containing the elements {1,2,3}\{1,2,3\}. Since all these vertices are endpoints of faulty edges, the 12 endpoints must consist of six copies of {1,2,3}\{1,2,3\}, 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 a={1,2,3}a = \{1,2,3\}, b1={1,2,4}b_1 = \{1,2,4\}, b2={1,2,5}b_2 = \{1,2,5\}, b3={1,3,5}b_3 = \{1,3,5\}, b4={1,3,6}b_4 = \{1,3,6\}, b5={2,3,6}b_5 = \{2,3,6\}, b6={2,3,4}b_6 = \{2,3,4\}, and F={ab1,ab2,ab3,ab4,ab5,ab6}F = \{ab_1,ab_2,ab_3,ab_4,ab_5,ab_6\}.

Let uu and vv be any two distinct vertices of J(6,3)J(6,3). We now discuss the following cases based on the distribution of these vertices in X(4)X(4) and Y(4)Y(4). It is clear that X−F=XX - F = X.

Case 1. u,v∈Xu,v \in X. Then NJ(6,3)−F(a)∩V(X)N_{J(6,3)-F}(a) \cap V(X) has only one vertex b7={1,3,4}b_7 = \{1,3,4\}.

Case 1.1. b7∈{u,v}b_7 \in\{u,v\}, say u=b7u = b_7. Note that b2={1,2,5}∈V(Y)b_2 = \{1,2,5\} \in V(Y). Let F1=F∖{ab2}F_1 = F \setminus\{ab_2\}. Since FF contains exactly four edges entirely within YY, F1F_1 leaves exactly three faulty edges in YY. By Lemma 6, J(5,3)J(5,3) is 3-edge-fault-tolerant, so there exists a Hamiltonian path in Y−F1Y - F_1 joining aa and b2b_2, denoted by ⟨a,Q1,b2⟩\langle a,Q_1,b_2\rangle. Choose a vertex b2′∈NX(b2)∩Xb'_2 \in N_X(b_2) \cap X such that b2′≠vb'_2 \ne v. Since X≅J(5,2)X \cong J(5,2) is a 6-regular graph on ten vertices, the vertex-deleted subgraph X−{u}X - \{u\} has nine vertices with a minimum degree of five. By the classic Ore-type condition for Hamiltonian connectivity (d(x)+d(y)≥5+5=10≥9+1d(x) + d(y) \ge5 + 5 = 10 \ge9 + 1), X−{u}X - \{u\} remains Hamiltonian-connected. Thus, there exists a Hamiltonian path in X−{u}X - \{u\} joining b2′b'_2 and vv, denoted by ⟨b2′,P1,v⟩\langle b'_2,P_1,v\rangle. Then the path ⟨u,a,Q1,b2,b2′,P1,v⟩\langle u,a,Q_1,b_2,b'_2,P_1,v\rangle is a Hamiltonian path in J(6,3)−FJ(6,3) - F joining uu and vv.

Case 1.2. b7∉{u,v}b_7 \notin\{u,v\}. Note that b2={1,2,5}b_2 = \{1,2,5\} has exactly three neighbors in XX. Since we only need to avoid the two vertices uu and vv, there exists at least one neighbor of b2b_2 in XX that is neither uu nor vv. Choose such a vertex as b2′′∈NX(b2)∩Xb''_2 \in N_X(b_2) \cap X. By Lemma 2, there exist two vertex-disjoint paths P11P_{11} and P12P_{12} of P2C(u,b7;v,b2′′)P_2C(u,b_7;v,b''_2) that cover XX. Adding the fault-free cross edges ab7ab_7 and b2b2′′b_2b''_2, and concatenating P11P_{11}, Q1Q_1, and P12P_{12} yields a Hamiltonian path in J(6,3)−FJ(6,3) - F joining uu and vv.

Case 2. u,v∈Yu,v \in Y. Recall that F1=F∖{ab2}F_1 = F \setminus\{ab_2\} leaves exactly 3 faulty edges in YY. By Lemma 6, there exists a Hamiltonian path Q2Q_2 in Y−F1Y - F_1 joining uu and vv. However, Q2Q_2 might contain the faulty edge ab2ab_2. We discuss the following two subcases based on whether ab2ab_2 is contained in Q2Q_2.

Case 2.1. ab2∈E(Q2)ab_2 \in E(Q_2). We choose two distinct vertices c1,c2∈Xc_1,c_2 \in X such that c1∈NX(a)c_1 \in N_X(a) and c2∈NX(b2)c_2 \in N_X(b_2). By Lemma 1, there exists a Hamiltonian path P2P_2 in X−FX-F joining c1c_1 and c2c_2. By deleting the edge ab2ab_2, adding the edges ac1ac_1 and b2c2b_2c_2, and concatenating these segments with P2P_2, we obtain a Hamiltonian path in J(6,3)−FJ(6,3)-F joining uu and vv.

Case 2.2. ab2∉E(Q2)ab_2 \notin E(Q_2). Then choose any edge p1p2∈E(Q2)p_1p_2 \in E(Q_2) and two distinct vertices c1′,c2′∈Xc'_1,c'_2 \in X such that c1′∈NX(p1)c'_1 \in N_X(p_1) and c2′∈NX(p2)c'_2 \in N_X(p_2). By Lemma 1, there exists a Hamiltonian path P2′P'_2 in X−FX-F joining c1′c'_1 and c2′c'_2. By deleting the edge p1p2p_1p_2, adding the cross edges p1c1′p_1c'_1 and p2c2′p_2c'_2, and concatenating the resulting segments of Q2Q_2 with P2′P'_2, we obtain a Hamiltonian path in J(6,3)−FJ(6,3)-F joining uu and vv.

Case 3. u∈Xu \in X and v∈Yv \in Y. Choose v′∈{b2,b3,b4,b5}∖{v}v' \in\{b_2,b_3,b_4,b_5\}\setminus\{v\}. By Table 2, there exists a Hamiltonian path in Y−FY-F joining b2b_2 and vv, denoted by ⟨b2,Q3,v⟩\langle b_2,Q_3,v\rangle. For any p∈NX(b2)∖{u}p \in N_X(b_2)\setminus\{u\}, by Lemma 1, there exists a Hamiltonian path in X−FX-F joining uu and pp, denoted by ⟨u,P3,p⟩\langle u,P_3,p\rangle. Then the path ⟨u,P3,p,b2,Q3,v⟩\langle u,P_3,p,b_2,Q_3,v\rangle is a Hamiltonian path in J(6,3)−FJ(6,3)-F joining uu and vv.

b2b_2vvHamiltonian path
125123⟨125,126,256,236,136,356,156,135,235,123⟩\langle125,126,256,236,136,356,156,135,235,123\rangle
125126⟨125,135,136,236,256,156,356,235,123,126⟩\langle125,135,136,236,256,156,356,235,123,126\rangle
125135⟨125,126,123,235,256,236,136,356,156,135⟩\langle125,126,123,235,256,236,136,356,156,135\rangle
125136⟨125,126,123,235,135,156,256,236,356,136⟩\langle125,126,123,235,135,156,256,236,356,136\rangle
125156⟨125,135,136,236,126,123,235,256,356,156⟩\langle125,135,136,236,126,123,235,256,356,156\rangle
125235⟨125,135,136,236,256,356,156,126,123,235⟩\langle125,135,136,236,256,356,156,126,123,235\rangle
125236⟨125,135,136,126,123,235,256,156,356,236⟩\langle125,135,136,126,123,235,256,156,356,236\rangle
125256⟨125,135,136,236,126,123,235,356,156,256⟩\langle125,135,136,236,126,123,235,356,156,256\rangle
125356⟨125,126,123,235,135,136,156,256,236,356⟩\langle125,126,123,235,135,136,156,256,236,356\rangle

Table 2. Hamiltonian paths in Y−FYY-F_Y joining b2={1,2,5}b_2=\{1,2,5\} and all other vertices in YY. For convenience, the set {i1,i2,i3}\{i_1,i_2,i_3\} is abbreviated as i1i2i3i_1i_2i_3.

Edge-fault-tolerant Hamiltonian Connectivity of J(n,k)J(n,k) 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 J(n,k)J(n,k) is k(n−k)−3k(n-k)-3. 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 uu and vv of J(4,2)J(4,2) and any matching F⊆E(J(4,2))F \subseteq E(J(4,2)), the graph J(4,2)−FJ(4,2)-F contains a Hamiltonian path joining uu and vv.

Proof. Since uu and vv are adjacent in J(4,2)J(4,2), there exists an element i∈u∖vi \in u \setminus v. Let X=X(i)={x∈V(J(4,2)):i∈x}X = X(i) = \{x \in V(J(4,2)) : i \in x\} and Y=Y(i)={y∈V(J(4,2)):i∉y}Y = Y(i) = \{y \in V(J(4,2)) : i \notin y\}. Then X≅K3X \cong K_3 and Y≅K3Y \cong K_3. Write V(X)={u1,u2,u3}V(X) = \{u_1,u_2,u_3\} and V(Y)={v1,v2,v3}V(Y) = \{v_1,v_2,v_3\}, where the vertices are indexed so that ujvj∉E(J(4,2))u_jv_j \notin E(J(4,2)) for j=1,2,3j = 1,2,3. Hence, E(X,Y)={ujvℓ:j≠ℓ}E(X,Y) = \{u_jv_\ell: j \ne\ell\}. Since u∈Xu \in X, v∈Yv \in Y, and uv∈E(J(4,2))uv \in E(J(4,2)), by relabeling the indices if necessary, we may assume that u=u2u = u_2, v=v1v = v_1. The decomposition of J(4,2)J(4,2) into two copies of K3K_3, together with the corresponding cross edges, is illustrated in Figure 1.

Figure 1. Structure of J(4,2)J(4,2) under the partition V(J(4,2))=X(i)∪Y(i)V(J(4,2)) = X(i) \cup Y(i), where X(i)≅Y(i)≅K3X(i) \cong Y(i) \cong K_3 and ujvℓ∈E(J(4,2))u_jv_\ell\in E(J(4,2)) if and only if j≠ℓj \ne\ell.

Case 1. F⊆E(X,Y)F \subseteq E(X,Y). In this case, all edges of XX and YY are fault-free. Consider the two cross edges u1v2u_1v_2 and u3v2u_3v_2. Since they share the vertex v2v_2 and FF is a matching, at most one of them belongs to FF. If u1v2∉Fu_1v_2 \notin F, then ⟨u2,u3,u1,v2,v3,v1⟩\langle u_2,u_3,u_1,v_2,v_3,v_1\rangle is a Hamiltonian path from uu to vv in J(4,2)−FJ(4,2)-F. If u1v2∈Fu_1v_2 \in F, then u3v2∉Fu_3v_2 \notin F, and hence ⟨u2,u1,u3,v2,v3,v1⟩\langle u_2,u_1,u_3,v_2,v_3,v_1\rangle is a Hamiltonian path from uu to vv in J(4,2)−FJ(4,2)-F.

Case 2. F∩(E(X)∪E(Y))≠∅F \cap(E(X) \cup E(Y)) \ne\varnothing.

By interchanging the roles of XX and YY if necessary, we may assume that F∩E(X)≠∅F \cap E(X) \ne\varnothing. Since X≅K3X \cong K_3 and FF is a matching, ∣F∩E(X)∣=1|F \cap E(X)| = 1. Extend FF to a maximal matching F′F' of J(4,2)J(4,2). Because the unique edge of F∩E(X)F \cap E(X) is incident with two of the three vertices of XX, each of the other two edges of E(X)E(X) shares an endpoint with it. Consequently, no additional edge of E(X)E(X) can be added when extending FF, and therefore ∣F′∩E(X)∣=1|F' \cap E(X)| = 1. Moreover, if a Hamiltonian path from uu to vv exists in J(4,2)−F′J(4,2)-F', then the same path also lies in J(4,2)−FJ(4,2)-F, since F⊆F′F \subseteq F'. Thus, it suffices to consider maximal matchings F′F' satisfying ∣F′∩E(X)∣=1|F' \cap E(X)| = 1.

Note that J(4,2)J(4,2) is isomorphic to the octahedral graph. With the terminals fixed as u=u2u = u_2 and v=v1v = v_1, there are exactly nine maximal matchings satisfying ∣F′∩E(X)∣=1|F' \cap E(X)| = 1: six perfect matchings of size 3 and three maximal matchings of size 2. By the symmetry of J(4,2)J(4,2) and the automorphisms preserving the terminal set {u2,v1}\{u_2, v_1\}, 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 u2u_2 to v1v_1, are listed in Table 3. Therefore, J(4,2)−F′J(4,2)-F' contains a Hamiltonian path from uu to vv in each case, and hence so does J(4,2)−FJ(4,2)-F.

SizeFaulty maximal matching FFHamiltonian path
3{u1u3,u2v1,v2v3}\{u_1u_3, u_2v_1, v_2v_3\}⟨u2,v3,u1,v2,u3,v1⟩\langle u_2, v_3, u_1, v_2, u_3, v_1\rangle
3{u1u3,u2v3,v1v2}\{u_1u_3, u_2v_3, v_1v_2\}⟨u2,u1,v3,v2,u3,v1⟩\langle u_2, u_1, v_3, v_2, u_3, v_1\rangle
2{u2u3,v2v3}\{u_2u_3, v_2v_3\}⟨u2,v3,u1,u3,v2,v1⟩\langle u_2, v_3, u_1, u_3, v_2, v_1\rangle
2{u1u2,v1v2}\{u_1u_2, v_1v_2\}⟨u2,v3,v2,u1,u3,v1⟩\langle u_2, v_3, v_2, u_1, u_3, v_1\rangle

Table 3. Hamiltonian paths in J(4,2)−FJ(4,2)-F joining u2u_2 and v1v_1 for all essentially different maximal matching faults.

Lemma 10. J(5,2)J(5,2) is matching-fault-tolerant Hamiltonian-connected.

Proof. Let uu and vv be two distinct vertices of J(5,2)J(5,2), and let FF be a set of faulty edges that forms a matching in J(5,2)J(5,2). Since u≠vu \ne v, there exists an element i∈[5]i \in[5] such that i∈ui \in u and i∉vi \notin v. Clearly, X(i)≅K4X(i) \cong K_4 and Y(i)≅J(4,2)Y(i) \cong J(4,2), with u∈X(i)u \in X(i) and v∈Y(i)v \in Y(i).

Since X(i)≅K4X(i) \cong K_4 and FF is a matching, X(i)−FX(i)-F always contains a cycle of length four. Consequently, there exists a Hamiltonian path in X(i)−FX(i)-F starting at uu, which we denote by ⟨u,u1,u2,u3⟩\langle u, u_1, u_2, u_3\rangle.

Next, we need to find a fault-free edge from u3u_3 to a vertex v1∈Y(i)v_1 \in Y(i) such that v1v_1 is adjacent to vv in Y(i)Y(i). Let u3={i,x}u_3 = \{i, x\} for some element x∈[5]x \in[5]. Since Y(i)Y(i) consists of all 2-subsets of [5]∖{i}[5] \setminus\{i\}, the vertex vv can be written as v={a,b}v = \{a, b\} where a,b≠ia, b \ne i. The neighbors of u3u_3 lying in Y(i)Y(i) consist of exactly three vertices, all of which contain xx. We consider two cases based on whether x∈vx \in v.

If x∈{a,b}x \in\{a,b\}, say x=ax = a, then v={a,b}v = \{a,b\} is itself a neighbor of u3u_3 in Y(i)Y(i). The other two neighbors of u3u_3 in Y(i)Y(i) must be of the form {a,c}\{a,c\} and {a,d}\{a,d\} where c,d∉{i,a,b}c,d \notin\{i,a,b\}. So they are adjacent to vv in Y(i)Y(i). If x∉{a,b}x \notin\{a,b\}, let [5]∖{i,x}={a,b,c}[5] \setminus\{i,x\} = \{a,b,c\}. The three neighbors of u3u_3 in Y(i)Y(i) are {x,a}\{x,a\}, {x,b}\{x,b\}, and {x,c}\{x,c\}. Notice that {x,a}\{x,a\} and {x,b}\{x,b\} each share exactly one element with v={a,b}v=\{a,b\}, meaning they are adjacent to vv in Y(i)Y(i).

In both cases, u3u_3 has at least two neighbors in Y(i)Y(i) that are adjacent to vv. Since FF is a matching, at most one edge incident to u3u_3 belongs to FF. Thus, there exists at least one fault-free edge from u3u_3 to a vertex v1∈Y(i)∖{v}v_1 \in Y(i) \setminus\{v\} such that v1v_1 is adjacent to vv. By Lemma 9, there exists a Hamiltonian path PP in Y(i)−FY(i)-F joining v1v_1 and vv. By adding the fault-free edge u3v1u_3v_1 and concatenating the path ⟨u,u1,u2,u3⟩\langle u,u_1,u_2,u_3\rangle with PP, we obtain a Hamiltonian path in J(5,2)−FJ(5,2)-F joining uu and vv.

We are now ready to present the main result of this section.

Theorem 11. For n≥5n \ge5 and 1≤k≤n−11 \le k \le n-1, J(n,k)J(n,k) is matching-fault-tolerant Hamiltonian-connected.

Proof. We prove the theorem by induction on nn.

For k=1k=1, since J(n,1)≅KnJ(n,1) \cong K_n, let M={a1b1,a2b2,⋯ ,atbt}M=\{a_1b_1,a_2b_2,\cdots,a_tb_t\} be a matching in KnK_n, and let U=V(J(n,1))∖⋃i=1t{ai,bi}={u1,u2,…,us}U=V(J(n,1)) \setminus\bigcup_{i=1}^{t}\{a_i,b_i\}=\{u_1,u_2,\ldots,u_s\} be the set of vertices not incident to any edge of MM. By symmetry, we enumerate Hamiltonian paths of essentially different terminals in Table 4. Since J(n,n−1)≅J(n,1)J(n,n-1)\cong J(n,1), the result also holds for k=n−1k=n-1. For n=5n=5 and k∈{2,3}k\in\{2,3\}, the result follows from Lemma 10.

Terminal pair {u,v}\{u,v\}Hamiltonian path in J(n,1)−MJ(n,1)-M
1{a1,b1}\{a_1,b_1\}⟨a1,…,at,u1,…,us,bt,…,b1⟩\langle a_1,\ldots,a_t,u_1,\ldots,u_s,b_t,\ldots,b_1\rangle
2{a1,a2}\{a_1,a_2\}⟨a1,a3,…,at,u1,…,us,bt,…,b1,a2⟩\langle a_1,a_3,\ldots,a_t,u_1,\ldots,u_s,b_t,\ldots,b_1,a_2\rangle
3{a1,u1}\{a_1,u_1\}⟨a1,…,at,u2,…,us,bt,…,b1,u1⟩\langle a_1,\ldots,a_t,u_2,\ldots,u_s,b_t,\ldots,b_1,u_1\rangle
4{u1,u2}\{u_1,u_2\}⟨u1,a1,…,at,u3,…,us,bt,…,b1,u2⟩\langle u_1,a_1,\ldots,a_t,u_3,\ldots,u_s,b_t,\ldots,b_1,u_2\rangle

Table 4. Hamiltonian paths for all representative terminal pairs in KnK_n under a matching fault.

Now assume that n≥6n \ge6 and 2≤k≤n−22 \le k \le n-2, and suppose that J(m,k′)J(m,k') is matching-fault-tolerant Hamiltonian-connected for every 5≤m<n5 \le m < n and 1≤k′≤m−11 \le k' \le m-1.

Since J(n,k)≅J(n,n−k)J(n,k)\cong J(n,n-k), we may assume that k≤n/2k \le n/2. Let FF be any matching of J(n,k)J(n,k), and let u,vu,v be any two distinct vertices of J(n,k)−FJ(n,k)-F. Since u≠vu \ne v, there exists an element i∈u∖vi \in u \setminus v. Let X=X(i)X=X(i) and Y=Y(i)Y=Y(i). Then X≅J(n−1,k−1)X\cong J(n-1,k-1), Y≅J(n−1,k)Y\cong J(n-1,k). Choose any vertex a∈X∖{u}a \in X \setminus\{u\}. Since aa contains ii, it has exactly n−kn-k neighbors in YY. Hence

∣NY(a)∖{v}∣≥n−k−1≥n2−1≥2.\lvert N_Y(a) \setminus\{v\} \rvert\ge n-k-1 \ge\frac{n}{2}-1 \ge2.

Since FF is a matching, at most one edge incident with aa belongs to FF. Therefore, among the edges joining aa to NY(a)∖{v}N_Y(a)\setminus\{v\}, there exists a non-faulty edge aa′aa' for some a′∈Y∖{v}a' \in Y\setminus\{v\}.

The restriction FXF_X of FF to E(X)E(X) is a matching, and similarly FYF_Y is a matching. By the induction hypothesis, there exists a Hamiltonian path ⟨u,P1,a⟩\langle u,P_1,a\rangle in X−FXX-F_X, and a Hamiltonian path ⟨a′,P2,v⟩\langle a',P_2,v\rangle in Y−FYY-F_Y. Since aa′∉Faa' \notin F, concatenating these paths with the edge aa′aa' gives ⟨u,P1,a,a′,P2,v⟩\langle u,P_1,a,a',P_2,v\rangle, which is a Hamiltonian uu-vv path of J(n,k)−FJ(n,k)-F. Thus J(n,k)J(n,k) 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 FF be a perfect matching of J(n,k)J(n,k), where n≥5n \ge5 and 1≤k≤n−11 \le k \le n-1. Then J(n,k)−FJ(n,k)-F is Hamiltonian-connected.

Vertex-fault-tolerant Hamiltonian connectivity of J(n,k)J(n,k)

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 J(6,3)J(6,3), deleting the six vertices

{1,2,3}, {1,3,4}, {1,4,6}, {3,4,5}, {3,5,6}, {4,5,6}\{1,2,3\},\ \{1,3,4\},\ \{1,4,6\},\ \{3,4,5\},\ \{3,5,6\},\ \{4,5,6\}

yields a subgraph containing no Hamiltonian path from {2,3,5}\{2,3,5\} to {2,4,5}\{2,4,5\}. 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 XX.

Lemma 13. For any two distinct vertices a,b∈Xa,b \in X, we have ∣NY(a)∣=∣NY(b)∣=n−k\lvert N_Y(a)\rvert=\lvert N_Y(b)\rvert=n-k and

∣NY(a)∩NY(b)∣={1,if a is adjacent to b;0,otherwise.\lvert N_Y(a)\cap N_Y(b)\rvert= \begin{cases} 1, & \text{if } a \text{ is adjacent to } b;\\ 0, & \text{otherwise.} \end{cases}

Proof. Since aa and bb are vertices in XX, they both contain the element ii. By definition, replacing the element ii in aa (or bb) with any element not currently in the set yields a neighbor in YY. Thus, ∣NY(a)∣=∣NY(b)∣=n−k\lvert N_Y(a)\rvert=\lvert N_Y(b)\rvert=n-k. We now determine the size of their common neighborhood based on their adjacency in XX.

Case 1. aa and bb are adjacent. Without loss of generality, let a={s1,i,t3,…,tk}a=\{s_1,i,t_3,\ldots,t_k\} and b={s2,i,t3,…,tk}b=\{s_2,i,t_3,\ldots,t_k\}, where s1≠s2s_1\ne s_2. To find a common neighbor in YY, we must replace the element ii in both sets such that the resulting sets are identical. The only way to achieve this is to replace ii in aa with s2s_2, and replace ii in bb with s1s_1. Thus, their unique common neighbor in YY is exactly {s1,s2,t3,…,tk}\{s_1,s_2,t_3,\ldots,t_k\}. Hence, ∣NY(a)∩NY(b)∣=1\lvert N_Y(a)\cap N_Y(b)\rvert=1.

Case 2. aa and bb are non-adjacent. Without loss of generality, let a={s1,p1,i,…,tk}a = \{s_1, p_1, i, \ldots, t_k\} and b={s2,p2,i,…,tk}b = \{s_2, p_2, i, \ldots, t_k\}, where {s1,p1}∩{s2,p2}=∅\{s_1, p_1\} \cap\{s_2, p_2\} = \varnothing. For any vertex v∈NY(a)v \in N_Y(a), vv must not contain ii (since v∈Yv \in Y), which means ii must be replaced by some element not in aa. Consequently, vv will still contain both s1s_1 and p1p_1. However, bb lacks both s1s_1 and p1p_1. A neighbor of bb in YY can acquire at most one of them (by replacing ii). Therefore, no vertex in NY(b)N_Y(b) can contain both s1s_1 and p1p_1, which implies v∉NY(b)v \notin N_Y(b). Thus, NY(a)∩NY(b)=∅N_Y(a) \cap N_Y(b) = \varnothing.

For the small base cases, we use exhaustive computational verification, which yields the following lemma.

Lemma 14. J(5,2)J(5, 2) and J(5,3)J(5, 3) 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 J(n,k)J(n, k).

Theorem 15. J(n,k)J(n, k) is (n−2)(n-2)-vertex-fault-tolerant Hamiltonian-connected whenever n≥5n \ge5 and 1≤k≤n−11 \le k \le n - 1.

Proof. We proceed by induction on nn. Since J(n,1)≅J(n,n−1)≅KnJ(n, 1) \cong J(n, n - 1) \cong K_n, the complete graph is trivially (n−2)(n - 2)-vertex-fault-tolerant Hamiltonian-connected. For the base cases n=5n = 5, J(5,2)J(5, 2) and J(5,3)J(5, 3) are 3-vertex-fault-tolerant Hamiltonian-connected by Lemma 14. Since J(n,k)≅J(n,n−k)J(n, k) \cong J(n, n - k), we may assume that k≤n/2k \le n/2.

For the inductive step, assume that n≥6n \ge6 and 2≤k≤n−22 \le k \le n - 2. The strong induction hypothesis asserts that J(m,k′)J(m, k') is (m−2)(m - 2)-vertex-fault-tolerant Hamiltonian-connected for any 5≤m<n5 \le m < n and 1≤k′≤m−11 \le k' \le m - 1. Let FF be a set of faulty vertices in J(n,k)J(n, k) with ∣F∣≤n−2|F| \le n - 2.

Consider two distinct arbitrary vertices uu and vv in J(n,k)−FJ(n, k) - F. Since u≠vu \ne v, there exists an element i∈[n]i \in[n] such that i∈ui \in u and i∉vi \notin v. We partition J(n,k)J(n, k) along ii, yielding X(i)≅J(n−1,k−1)X(i) \cong J(n - 1, k - 1) and Y(i)≅J(n−1,k)Y(i) \cong J(n - 1, k), with u∈X(i)u \in X(i) and v∈Y(i)v \in Y(i). Let FXF_X and FYF_Y denote the restriction of FF on X(i)X(i) and Y(i)Y(i), respectively. We consider two subcases based on the fault distribution.

Case 1. 1≤∣FX∣≤n−31 \le|F_X| \le n - 3 and 1≤∣FY∣≤n−31 \le|F_Y| \le n - 3. We first select candidate endpoints in X(i)X(i) to cross into Y(i)Y(i). The number of available fault-free vertices in X(i)X(i) other than uu is ∣X(i)∣−∣FX∣−1|X(i)| - |F_X| - 1. If we can choose two distinct candidates a,b∈X(i)∖(FX∪{u})a, b \in X(i) \setminus(F_X \cup\{u\}), then by Lemma 13, the cardinality of the neighborhood of {a,b}\{a, b\} in Y(i)Y(i) satisfies:

∣NY({a,b})∣≥2(n−k)−1=(n−k)+(n−k)−1≥(n−k)+k−1(since n≥2k)=n−1.\begin{aligned} |N_Y(\{a,b\})| &\ge2(n-k)-1 \\ &= (n-k)+(n-k)-1 \\ &\ge(n-k)+k-1 \qquad(\text{since } n \ge2k) \\ &= n-1. \end{aligned}

Since ∣FY∪{v}∣≤∣FY∣+1≤(n−3)+1=n−2|F_Y \cup\{v\}| \le|F_Y| + 1 \le(n - 3) + 1 = n - 2, we have ∣NY({a,b})∣≥n−1>∣FY∪{v}∣|N_Y(\{a,b\})| \ge n - 1 > |F_Y \cup\{v\}|. Thus, there exists at least one fault-free cross edge to Y(i)Y(i). Note that we can always find two such candidates a,ba,b unless k=2k=2 and ∣FX∣=n−3|F_X|=n-3. In this extreme scenario, only one candidate aa remains in X(i)X(i), but consequently ∣FY∣≤(n−2)−(n−3)=1|F_Y|\le(n-2)-(n-3)=1. The single candidate aa has ∣NY(a)∣=n−2≥4|N_Y(a)|=n-2\ge4 neighbors in Y(i)Y(i), which is greater than ∣FY∪{v}∣≤2|F_Y\cup\{v\}|\le2, ensuring a fault-free cross edge.

Without loss of generality, let c∈Y(i)∖(FY∪{v})c\in Y(i)\setminus(F_Y\cup\{v\}) be a fault-free neighbor of bb. By the induction hypothesis, there exists a Hamiltonian path ⟨u,P1,b⟩\langle u,P_1,b\rangle in X(i)−FXX(i)-F_X, and a Hamiltonian path ⟨c,P2,v⟩\langle c,P_2,v\rangle in Y(i)−FYY(i)-F_Y. Concatenating them via the edge bcbc yields a Hamiltonian path ⟨u,P1,b,c,P2,v⟩\langle u,P_1,b,c,P_2,v\rangle in J(n,k)−FJ(n,k)-F.

Case 2. ∣FX∣=0|F_X|=0 or n−2n-2. We only consider FX=∅F_X=\varnothing as the case FY=∅F_Y=\varnothing can be handled symmetrically. Let ff be a faulty vertex in FYF_Y. Then, the remaining faults satisfy ∣FY∖{f}∣≤n−3|F_Y\setminus\{f\}|\le n-3.

By the induction hypothesis, there exists a Hamiltonian path from ff to vv in Y(i)−(FY∖{f})Y(i)-(F_Y\setminus\{f\}), denoted by ⟨f,f′,Q2,v⟩\langle f,f',Q_2,v\rangle, where f′f' is the immediate neighbor of ff. Since ff is faulty, we truncate it to obtain a fault-free path segment ⟨f′,Q2,v⟩\langle f',Q_2,v\rangle in Y(i)−FYY(i)-F_Y. Because k≥2k\ge2, the vertex f′f' has k≥2k\ge2 neighbors in X(i)X(i). Thus, we can choose a neighbor f′′∈NX(i)(f′)f''\in N_{X(i)}(f') such that f′′≠uf''\ne u. By the induction hypothesis on X(i)X(i), there exists a Hamiltonian path ⟨u,Q1,f′′⟩\langle u,Q_1,f''\rangle in X(i)X(i). Connecting the two segments via the cross edge f′′f′f''f', the path ⟨u,Q1,f′′,f′,Q2,v⟩\langle u,Q_1,f'',f',Q_2,v\rangle is a fault-free Hamiltonian path joining uu and vv in J(n,k)−FJ(n,k)-F.

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 J(n,k)J(n,k). 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

J(n,k)≅J(n,n−k).J(n,k)\cong J(n,n-k).

Specifically, whenever k>n/2k>n/2, each vertex is replaced by its complement in [n][n], the parameter kk is replaced by n−kn-k, 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 k≤n/2k \le n/2.

When the recursion reaches k=1k = 1 (or, equivalently, k=n−1k = n - 1), the problem reduces to Hamiltonian routing in a faulty complete graph. Let G=Kn−FG = K_n - F, where ∣F∣≤n−4|F| \le n - 4. For every pair of nonadjacent vertices x,yx, y in GG, we have xy∈Fxy \in F and

dF(x)+dF(y)≤∣F∣+1≤n−3.d_F(x) + d_F(y) \le|F| + 1 \le n - 3.

Consequently,

dG(x)+dG(y)=2(n−1)−dF(x)−dF(y)≥n+1.d_G(x) + d_G(y) = 2(n - 1) - d_F(x) - d_F(y) \ge n + 1.

Thus, GG 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 n−4n - 4 faulty edges are processed and each path rearrangement requires at most a linear scan of the current path, a single invocation takes O(n2)O(n^2) time.

Since J(4,2)J(4,2) and J(5,2)J(5,2) 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 J(6,3)J(6,3) 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 O(1)O(1) time.

The structural correctness and termination of Algorithm 1 follow directly from the constructive proof of Theorem 7. We now analyze its complexity. Let N=(nk)N = \binom{n}{k} denote the total number of vertices in J(n,k)J(n,k).

Theorem 16. For 4≤k≤n−44 \le k \le n - 4, Algorithm 1 constructs a fault-free Hamiltonian path in asymptotically optimal Θ(N)\Theta(N) time, where N=(nk)N = \binom{n}{k}.

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 O(N)O(N).

Let DD be the maximum recursion depth. At each recursive step, the first graph parameter decreases from nn to n−1n - 1, and therefore

D=O(n).D = O(n).
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 dd, let Rd\mathcal{R}_d 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,

∑R∈Rd∣FR∣≤∣F∣.\sum_{R \in\mathcal{R}_d} |F_R| \leq|F|.

For each faulty edge xy∈FRxy \in F_R, Algorithm 2 (updating the counters) needs O(n)O(n) time. Thus the aggregate partition-selection cost at one recursion depth is

O(n∑R∈Rd∣FR∣)=O(n∣F∣).O\left(n \sum_{R \in\mathcal{R}_d} |F_R|\right) = O(n|F|).

Summing over all O(n)O(n) recursion levels gives

Tpartition=O(n2∣F∣).T_{\mathrm{partition}} = O(n^2|F|).

Since

∣F∣≤k(n−k)−3≤n24,|F| \leq k(n-k)-3 \leq\frac{n^2}{4},

we obtain

Tpartition=O(n4).T_{\mathrm{partition}} = O(n^4).

For 4≤k≤n−44 \le k \le n - 4,

N=(nk)≥(n4)=Θ(n4).N = \binom{n}{k} \ge\binom{n}{4} = \Theta(n^4).

and hence

Tpartition=O(N).T_{\mathrm{partition}} = O(N).

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 R≅KmRR \cong K_{m_R}, let FRF_R denote its internal faulty-edge set. A call to CompleteGraphRouting on RR requires O(mR(∣FR∣+1))O(m_R(|F_R| + 1)) time. Since these complete-graph leaves are vertex-disjoint,

∑RmR≤N,∑R∣FR∣≤∣F∣.\sum_R m_R \le N, \qquad\sum_R |F_R| \le|F|.

Moreover, mR≤nm_R \le n for every complete-graph leaf. Hence,

Tcomplete=O(N+n∣F∣)=O(N+n3)=O(N).T_{\mathrm{complete}} = O(N + n|F|) = O(N + n^3) = O(N).

The fixed-size routines SmallGraphRouting and SpecialJ63Routing contribute only O(N)O(N) aggregate time. Combining all components,

T(N)=O(N).T(N) = O(N).

Since explicitly outputting a Hamiltonian path containing all NN vertices requires Ω(N)\Omega(N) time, we conclude that

T(N)=Θ(N).T(N) = \Theta(N).

Thus, Algorithm 1 is asymptotically optimal.

The boundary cases k=2k = 2 and 33 require separate consideration. For both cases, the admissible number of general edge faults is linear in nn. Since the recursion depth is O(n)O(n), the above partition-selection analysis gives an aggregate overhead of O(n3)O(n^3). For k=3k = 3, we have

N=(n3)=Θ(n3),N = \binom{n}{3} = \Theta(n^3),

and hence the partition-selection overhead remains O(N)O(N). For k=2k = 2, however,

N=(n2)=Θ(n2),N = \binom{n}{2} = \Theta(n^2),

so the same analysis yields the conservative bound

O(n3)=O(N3/2).O(n^3) = O(N^{3/2}).

Thus, under the direct implementation of Algorithm 2, the present analysis does not establish a linear-in-NN worst-case bound for k=2k = 2. 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 FF is pre-processed into a hash-based data structure, enabling O(1)O(1) 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 Θ(N)\Theta(N) 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 T(n,k)T(n,k) denote the time required to construct the Hamiltonian path in J(n,k)J(n,k). Thus, the recurrence relation can be formulated as:

T(n,k)=T(n−1,k−1)+T(n−1,k)+Tbridge(n,k)+O(1),T(n,k)=T(n-1,k-1)+T(n-1,k)+T_{\mathrm{bridge}}(n,k)+O(1),

Algorithm 4: Bridge Selection for Matching and Vertex Faults

Input: Subgraphs XX, YY; Terminals uu, vv; Fault sets FXF_X, FYF_Y; FaultType; Global fault set FF

Output: A valid fault-free cross-edge (a,c)(a,c) bridging XX and YY

Function FindBridge(X,Y,u,v,FX,FY,FaultType,F)(X,Y,u,v,F_X,F_Y,\mathrm{FaultType},F):

if FaultType == Matching then

Select an arbitrary candidate a∈X∖{u}a \in X \setminus\{u\};

foreach c∈NY(a)∖{v}c \in N_Y(a) \setminus\{v\} do

if (a,c)∉F(a,c) \notin F then

return (a,c)(a,c);

else if FaultType == Vertex then

if 1≤∣FX∣≤n−31 \le|F_X| \le n-3 and 1≤∣FY∣≤n−31 \le|F_Y| \le n-3 then

Select a set C⊆X∖(FX∪{u})C \subseteq X \setminus(F_X \cup\{u\}) with size min⁡(2,∣X∖(FX∪{u})∣)\min(2, |X \setminus(F_X \cup\{u\})|);

foreach a∈Ca \in C do

Select two distinct vertices c1,c2∈NY(a)∖{v}c_1,c_2 \in N_Y(a) \setminus\{v\};

if ac1∉Fac_1 \notin F then return (a,c1)(a,c_1);

else

return (a,c2)(a,c_2)

else

if FY≠∅F_Y \ne\varnothing then f←f \gets any node in FYF_Y;

else f←f \gets any node in Y∖{v}Y \setminus\{v\};

Select a fault-free neighbor f′∈NY(f)∖FYf' \in N_Y(f) \setminus F_Y;

Select a fault-free neighbor f′′∈NX(f′)∖{u}f'' \in N_X(f') \setminus\{u\};

return (f′′,f′)(f'',f'); // Return a fault-free bridge

where Tbridge(n,k)T_{\mathrm{bridge}}(n,k) is the time complexity of selecting a valid fault-free cross-edge.

Instead of exhaustively scanning the O(n)\mathcal{O}(n) cross-neighbors for a selected candidate a∈X(i)a \in X(i), we exploit the structural constraints of the fault models to achieve O(1)\mathcal{O}(1) bridge selection:

  • Under matching faults: Since the fault set is a matching, at most one faulty edge is incident to any vertex aa. Therefore, the algorithm only generates at most two candidate cross-neighbors via elementary set operations (e.g., a∖{j}∪{i}a \setminus\{j\} \cup\{i\}) and test them using O(1)\mathcal{O}(1) queries.

  • Under vertex faults: Whether selecting an arbitrary pair a,ba,b (when faults are distributed) or arbitrarily picking an fault node ff in FXF_X (when FX=∅F_X = \varnothing), the initial selections require no heuristic search and execute in strict O(1)\mathcal{O}(1) time.

To locate the required intermediate fault-free neighbor, the algorithm utilizes O(1)O(1) hash queries in total.

Consequently, Tbridge(n,k)=O(1)T_{\mathrm{bridge}}(n,k)=O(1). The recurrence relation thus simplifies to:

T(n,k)≤T(n−1,k−1)+T(n−1,k)+O(1).T(n,k) \le T(n-1,k-1) + T(n-1,k) + O(1).

Notice that the size of the graph precisely follows Pascal’s identity:

N(n,k)=(nk)=(n−1k−1)+(n−1k).N(n,k) = \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.

By induction, solving this recurrence yields T(n,k)=O(N(n,k))=O(N)T(n,k)=O(N(n,k))=O(N). Furthermore, any algorithm that constructs and outputs a Hamiltonian path must sequentially visit and output all NN vertices, which requires at least Ω(N)\Omega(N) time. Combining the upper and lower bounds, we conclude that the total time complexity is T(n,k)=Θ(N)T(n,k)=\Theta(N), 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 J(16,k)J(16,k) for 2≤k≤82 \le k \le8. 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 J(16,k)J(16,k), 2≤k≤82 \le k \le8, corresponding to network sizes ranging from N=120N=120 to N=12,870N=12{,}870. The fault configurations contain k(n−k)−3k(n-k)-3 general faulty edges, a faulty-edge set forming a perfect matching, and n−2n-2 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.

Empirical runtime of fault-tolerant Hamiltonian routing algorithms

Figure 2. Average execution time (AET) versus network size NN for the proposed Hamiltonian routing algorithms under general edge, matching, and vertex faults in J(16,k)J(16, k), 2≤k≤82 \le k \le8. 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 NN increases from 120 to 12,870, the AET increases from 2.76×10−32.76 \times10^{-3} to 3.00×10−13.00 \times10^{-1} s under general edge faults, from 2.49×10−32.49 \times10^{-3} to 3.18×10−13.18 \times10^{-1} s under matching faults, and from 1.83×10−31.83 \times10^{-3} to 2.74×10−12.74 \times10^{-1} s under vertex faults. Linear regressions of AET against NN yield coefficients of determination of R2=R^2= 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 NN 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 J(16,8)J(16, 8), 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 J(16,8)J(16, 8) 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 J(n,k)J(n,k), a highly symmetric graph with potential as a topology for multiprocessor systems. We first established that J(n,k)J(n,k) is (k(n−k)−3)(k(n-k)-3)-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 J(n,k)J(n,k) remains Hamiltonian-connected under any matching fault for n≥5n \ge5. Finally, addressing the destructive nature of node failures, we demonstrated that J(n,k)J(n,k) is (n−2)(n-2)-vertex-fault-tolerant Hamiltonian-connected.

When comparing the Johnson network J(n,k)J(n,k) with bipartite multiprocessor topologies such as the hypercube QnQ_n and the star graph SnS_n, 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, J(n,k)J(n,k) 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 J(n,k)J(n,k) is yet to be determined. As demonstrated by our exhaustive computer search on J(6,3)J(6,3), 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 δ(J(n,k)−F)≥3\delta(J(n,k)-F) \ge3 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. [1]C. Godsill and G. Royle, Algebraic Graph Theory. New York: Springer, 2001.
  2. [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. [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. [4]——, “Spectrum of johnson graphs,” Discrete Mathematics, vol. 346, no. 3, p. 113262, 2023.DOI
  5. [5]B. Alspach, “Hamilton paths in cayley graphs on coxeter groups: I,” Ars Mathematica Contemporanea, vol. 8, pp. 35–53, 2015.DOI
  6. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [20]B. Alspach, “Johnson graphs are hamilton-connected,” Ars Mathematica Contemporanea, vol. 6, pp. 21–23, 2013.DOI
  21. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [32]T. Lan and H. Lü, “Hamiltonian cycles of balanced hypercube with disjoint faulty edges,” Information Processing Letters, vol. 187, p. 106518, 2025.
  33. [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. [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. [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. [36]S.-Y. Hsieh, “Some edge-fault-tolerant properties of the folded hypercube,” Networks, vol. 51, no. 2, pp. 92–101, 2008.
  37. [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. [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

Paper details

vlnc:W_jyxurn35
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents