Johnson graphs maintain strong paths despite multiple failures
Fault-tolerant Hamiltonian connectivity of Johnson graphs
Discrete Mathematics
Summary
Johnson graphs are special network structures where any two points can be connected by a path that visits every node exactly once. This paper shows that even if some connections or points fail or are removed, these networks still allow such special paths to exist in many cases. The authors provide ways to find these paths efficiently even after different types of failures. Their work includes tests on large networks, showing the methods work well and quickly.
What this means in practice
- •For network designers: Ensure resilient routing in highly symmetric network topologies when some nodes or links fail, using the paper’s fault-tolerant Hamiltonian path methods.
- •For distributed computing engineers: Implement efficient fault-tolerant communication protocols that maintain guaranteed end-to-end paths despite multiple failures in network components.
Authors
Huazhong Lü, Jinhao Liu
Abstract
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.