PaperlayerView exact revision on arXiv

Source-linked AI summary

Fault-tolerant Hamiltonian connectivity of Johnson graphs

Huazhong Lü, Jinhao Liu

arXiv:2609.12617v1cs.DM

TL;DR

The paper asks how well Johnson graphs preserve Hamiltonian connectivity when links or processors fail. It proves fault-tolerance results for unrestricted edge faults, matching faults, and vertex faults, and derives recursive routing algorithms; simulations report runtime close to linear over the tested range.

  • Problem

    Although Johnson graphs are Hamiltonian-connected without faults, the extent to which this property survives edge and vertex failures remains a comparatively limited area of study.

    Source: §1 · p. 2

  • Method

    The paper gives constructive proofs of Hamiltonian connectivity under three fault models and derives recursive routing algorithms from those proofs.

    Source: §6 · p. 26

  • Results

    The paper proves tolerance of k(n-k)-3 edge faults, arbitrary matching faults for n ≥5, and n-2 vertex faults; measured runtimes are well approximated by linear functions of network size over the tested range.

    Source: §5.3 · p. 25, §6 · p. 26

  • Takeaways & Limitations

    Johnson graphs retain Hamiltonian connectivity across unrestricted edge, matching, and vertex failure models, providing a framework for fault-tolerant Hamiltonian routing.

    Source: §6 · p. 26

    The optimal vertex-fault tolerance bound remains unknown, and the edge-fault analysis does not establish a linear-in-N worst-case bound for the direct k=2 implementation.

    Source: §5.1 · p. 21, §6 · p. 26

Abstract

from arXiv · show

Johnson graphs $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)$ remains Hamiltonian-connected after the deletion of any set of at most $k(n-k)-3$ edges for $n\geq4$. Since $J(n,k)$ is $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)$ remains Hamiltonian-connected after the deletion of an arbitrary matching for $n\geq5$, including a perfect matching whenever one exists. For vertex failures, we prove that $J(n,k)$ is $(n-2)$-vertex-fault-tolerant Hamiltonian-connected for $n\geq5$. All three results are constructive and lead to recursive fault-tolerant Hamiltonian routing algorithms. Simulation results on Johnson graphs with up to $12{,}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.

1. Introduction

Hamiltonian connectivity provides spanning paths between any two vertices, a property studied for Johnson graphs in the fault-free setting and relevant to interconnection networks. This introduction motivates fault-tolerant connectivity and presents results for unrestricted edge faults, matching faults, and vertex failures.

Motivation

  • Hamiltonian connectivity guarantees a spanning path between every pair of vertices; the fault-free property is known for Johnson graphs and is relevant to network routing.The introduction connects Hamiltonian paths with linear-array processor organization and notes their potential to reduce deadlocks and congestion in multicast routing.Source: §1 · p. 2

Research gap

  • Fault-tolerant Hamiltonian connectivity remains relatively underexplored for Johnson graphs, motivating questions about edge-fault limits, matching faults, and vertex failures.The introduction frames the unrestricted edge-fault threshold as a reliability question and asks whether matching faults can be tolerated even at perfect-matching scale.Source: §1 · p. 3

General edge faults

  • The edge-fault result tolerates up to k(n-k)-3 faulty edges, reaching the degree-based upper bound for J(n,k).The graph is k(n-k)-regular, and the bound is identified as the natural upper bound imposed by the minimum-degree obstruction.Source: §1 · pp. 3–4

Matching faults

  • Under matching faults, Hamiltonian connectivity persists even when the faulty edges form a perfect matching, whenever one exists.Restricting failures to pairwise disjoint edges prevents multiple faulty links from concentrating at one vertex and permits larger fault sets.Source: §1 · pp. 3–4

Vertex faults

  • After removal of at most n-2 vertices, every pair of remaining fault-free vertices can still be joined by a Hamiltonian path spanning all remaining vertices.Source: §1 · p. 4

Routing algorithms

  • The constructive proofs yield recursive fault-tolerant Hamiltonian routing algorithms for all three fault models.The paper presents these results as a systematic framework for routing under diverse failure patterns.Source: §1 · p. 4

2. Optimal Edge-fault-tolerant Hamiltonian Connectivity of J(n, k)

For n ≥ 4, J(n, k) tolerates k(n − k) − 3 arbitrary edge faults while remaining Hamiltonian-connected, attaining its degree-based upper bound. The proof is recursive, with a separate treatment of J(6, 3).

2. Optimal Edge-fault-tolerant Hamiltonian Connectivity of J(n, k)

  • The proof establishes small cases directly, including J(4, 2) with one edge fault and J(5, 2) and J(5, 3) with three.The small-network base cases were exhaustively checked over admissible fault sets and endpoint pairs.Source: §2 · p. 6
  • The bound is optimal: a graph of minimum degree δ cannot generally tolerate more than δ − 3 edge faults, and J(n, k) is k(n − k)-regular.With δ − 2 incident edges faulty at one vertex, only two fault-free neighbors remain, preventing a spanning path between them.Source: §2 · p. 6
  • For n ≥ 4, J(n, k) is (k(n − k) − 3)-edge-fault-tolerant Hamiltonian-connected.The theorem covers 1 ≤ k ≤ n − 1.Source: §2 · p. 6
  • The inductive proof partitions J(n, k) into X and Y, finds Hamiltonian paths within the layers, and joins or patches them with fault-free cross-edges.The argument handles endpoint pairs lying in either layer or in different layers.Source: §2 · pp. 6, 8, 9
  • J(6, 3) is handled separately when the induction’s layer-fault condition fails; under that exceptional configuration, the graph remains Hamiltonian-connected.The exceptional case has |A| = |B| = 3 and |F_Y(j)| ≥ 4 for every j ∈ B.Source: §2 · pp. 8–9

3. Edge-fault-tolerant Hamiltonian Connectivity of J(n, k) under Matching Faults

For n ≥ 5, Johnson graphs remain Hamiltonian-connected after any matching of faulty edges is removed. This includes a perfect matching whenever one exists.

3. Edge-fault-tolerant Hamiltonian Connectivity of J(n, k) under Matching Faults

  • The base case J(4, 2) handles adjacent endpoints by splitting the graph into two K3 layers and constructing a path for each matching-fault arrangement.For J(5, 2), the paper also establishes matching-fault-tolerant Hamiltonian connectivity.Source: §3 · pp. 12–13
  • For n ≥ 5, J(n, k) remains Hamiltonian-connected after deletion of an arbitrary matching.The result covers 1 ≤ k ≤ n − 1.Source: §3 · p. 14
  • Induction partitions J(n, k) into layers X and Y, constructs a Hamiltonian path in each fault-restricted layer, and joins them with a fault-free cross-edge.Because the faulty edges form a matching, at most one edge incident to a chosen vertex is faulty.Source: §3 · p. 14
  • The guarantee includes deletion of a perfect matching whenever one exists.The paper states this as a corollary for n ≥ 5 and 1 ≤ k ≤ n − 1.Source: §3 · p. 14

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

For n ≥ 5, J(n, k) remains Hamiltonian-connected after removal of any n − 2 vertices. An inductive proof partitions the graph into layers and connects paths across them.

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

  • A degree-based edge-fault guarantee does not generally transfer to vertex faults: in J(6, 3), the listed six deleted vertices leave no Hamiltonian path between the specified endpoints.Source: §4 · p. 15
  • Exhaustive verification establishes the base case that J(5, 2) and J(5, 3) tolerate three vertex faults.Source: §4 · p. 16
  • For n ≥ 5, J(n, k) is (n − 2)-vertex-fault-tolerant Hamiltonian-connected for 1 ≤ k ≤ n − 1.Source: §4 · p. 16
  • The proof partitions J(n, k) into X(i) and Y(i), then uses inductive Hamiltonian paths in the layers joined by a fault-free cross-edge.For a difficult fault distribution, two candidate vertices in X(i) provide enough cross-layer neighbors to find a fault-free connection.Source: §4 · pp. 16–17
  • When all faults lie in Y(i), the proof removes a faulty vertex from an inductively obtained path and joins the remaining path to one in X(i).The selected neighbor in X(i) is chosen to differ from the source endpoint u.Source: §4 · p. 17

5. Fault-Tolerant Algorithm and Complexity Analysis

The section presents divide-and-conquer routing algorithms for the three fault models and analyzes their complexity and performance on J(16, k). Simulation results report comparable practical efficiency across the models, with execution times dependent on the Python implementation.

5.1 Routing under General Edge Faults

  • For 4 ≤ k ≤ n − 4, Algorithm 1 runs in optimal Θ(N) time; partition-selection overhead is O(N) at k = 3, but the analysis does not establish linear time at k = 2.The k = 2 limitation applies to the direct implementation of Algorithm 2; the section notes that specialized or incrementally maintained partition selection may reduce this overhead.Source: §5.1 · pp. 18, 21

5.2 Routing under Matching and Vertex Faults

  • Algorithm 3 achieves optimal Θ(N) time for matching and vertex faults, using O(1) bridge selection through fault-model-specific candidate checks and hash-based fault queries.The analysis assumes the fault set is preprocessed into a hash-based structure with O(1) average-time membership queries.Source: §5.2 · pp. 22–24

5.3 Simulation and Performance Evaluation

  • AET rose from 2.76 × 10−3 to 3.00 × 10−1 s (general edge), 2.49 × 10−3 to 3.18 × 10−1 s (matching), and 1.83 × 10−3 to 2.74 × 10−1 s (vertex) as N grew from 120 to 12,870.All 100 trials per tested network size and fault model produced valid fault-free Hamiltonian paths. Linear regressions yielded R2 = 0.9990, 0.9978, and 0.9982 for general-edge, matching, and vertex faults, respectively.Source: §5.3 · pp. 24–25
  • The vertex-fault algorithm reached approximately 0.274 s AET for J(16, 8), versus approximately 0.300 s for general-edge and 0.318 s for matching faults, with no qualitatively different growth behavior.The plotted AET data average 100 randomly selected source-destination pairs at the maximum fault cardinality guaranteed by each result.Source: §5.3 · p. 25, Figure 2 · p. 25
  • Matching-fault routing handled a perfect matching of 6,435 faulty edges for J(16, 8), compared with 61 arbitrary faulty edges under general-edge faults, while retaining comparable routing time.The matching-fault model permits more faulty edges because of its structural restriction.Source: §5.3 · p. 25
  • Because the algorithms were implemented in Python, absolute execution times are implementation-dependent, although the observed growth trend agrees with the theoretical scalability analysis.Source: §5.3 · p. 25

6. Conclusion

The conclusion establishes fault tolerance for three failure patterns in J(n,k) and presents arbitrary-endpoint Hamiltonian paths as a topology advantage, while leaving the tight vertex-fault bound unresolved.

6. Conclusion

  • J(n,k) is (k(n-k)-3)-edge-fault-tolerant Hamiltonian-connected, remains Hamiltonian-connected under any matching fault for n ≥ 5, and is (n-2)-vertex-fault-tolerant Hamiltonian-connected.The conclusion says the general edge-fault bound attains the natural degree-based upper bound.Source: §6 · p. 26
  • Unlike bipartite topologies, J(n,k) guarantees Hamiltonian paths between any two fault-free vertices, providing unrestricted endpoint flexibility for spanning linear structures.The passage identifies this flexibility, together with fault tolerance, as highlighting Johnson graphs' potential as robust interconnection topologies.Source: §6 · p. 26
  • The optimal upper bound for vertex-fault tolerance remains undetermined, and the degree-minus-three edge-fault bound does not extend to vertex faults in J(6,3).The conclusion also identifies conditional edge-fault models under residual minimum degree δ(J(n,k) − F) ≥ 3 as a direction for further study.Source: §6 · p. 26
Loading 2609.12617v1…