CS Paper Radar

Fault-tolerant Hamiltonian connectivity of Johnson graphs

Huazhong Lü, Jinhao Liu

cs.DM ·submitted 2026-09-11 09:18 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Hamilton Cycles in 10-Tough $(2P_2 \cup P_1)$-Free Graphs

cs.DM math.CO ·2026-08-25 ·Qiuyu Chen
theory similarity 0.70
Abstract · 16 pages, no figures

A graph is called 10-tough and $(2P_2 \cup P_1)$-free if every vertex set whose deletion leaves at least two components has cardinality at least ten times the number of those components and if the graph has no induced subgraph consisting of two disjoint edges and an isolated vertex. We prove that every finite simple 10-tough $(2P_2 \cup P_1)$-free graph on at least three vertices is Hamiltonian. The proof splits according to whether some edge has joint neighbourhood of order at most $4n/11$. In the small-neighbourhood case, a matched path-cover is compressed to a prescribed matching. In the large-neighbourhood case, an asymmetric analysis of the two components left by a putative small cut yields the required connectivity bound. A Hamilton cycle through the prescribed edges is then expanded, and a cycle-extension lemma inserts the remaining vertices.

0.09

A Necessary and Sufficient Hall Condition for Hypergraphs

cs.DM math.COcs.DS ·2026-08-10 ·Xiaoyao Huang
theory similarity 0.63
Abstract · 17 pages, 3 figures; new content in sections 1 and 4

We prove a necessary and sufficient Hall condition for a family $A=(A_e)_{e\in E(G)}$ of hypergraphs indexed by the edges of a forest \(G\). This restriction on the index graph is sharp. The loop-only case recovers the classical Hall's Theorem with multiplicities for arbitrary finite set systems, while the loopless case shows that full rainbow matching is polynomial time solvable under this forest structure, although the problem is NP-complete in general. As another application, we prove every $5$-tough chordal graph is Hamilton-connected, improving toughness bounds of $18$ for Hamiltonicity (1998) and $10$ for Hamilton-connectedness (2017).

0.44

Solving Vertex Integrity Faster than $2^n$

cs.DS cs.DM ·2026-09-27 ·Sandip Das, Sweta Das, Sk Samim Islam, Ritam Manna Mitra, Aashirwad Mohapatra +1 more
theory similarity 0.60
Abstract · 14 Pages, 1 figure

Vertex Integrity is a classical graph parameter measuring the vulnerability of a network to vertex failures. We settle two fundamental questions concerning its exact exponential complexity. First, we prove that, unless the Exponential Time Hypothesis fails, Vertex Integrity has no $2^{o(n)}n^{O(1)}$-time algorithm. Secondly, we give a deterministic exact algorithm running in $O(1.9602^n)$ time and space, improving the straightforward $O(2^n)$ bound.

0.25

Edge-structure fault diameters of exchanged hypercubes

cs.DM ·2026-10-31 ·Lihui Dong, Zhuo Li
similarity 0.60
Abstract

We determine the edge-structure and edge-substructure fault diameters of the exchanged hypercube $EH(s,t)$ for every $1\le s\le t$. Both parameters equal $s+t+4$, two more than the fault-free diameter, except for $EH(2,2)$, where both are nine, and $EH(1,1)$, where they are five and six, respectively. This holds even though an admissible family may remove up to $2s$ vertices, more than the vertex connectivity $s+1$. For every $s\ge2$, the maximum is attained by $s$ parallel fault edges in class $0$. For $s\ge3$, the structure-fault diameter exceeds the classical $s$-vertex-fault diameter by exactly one.

0.25

Optimal-Size Strong Connectivity Preservers under Two Edge Failures in Subcubic Time

cs.DS ·2026-11-12 ·Wanhee Lee, Chenglin Fan
theory similarity 0.60
Abstract · 43 pages

A $k$-edge-failure strong connectivity preserver of a directed graph on $N$ vertices is a spanning subgraph that has the same strongly connected components as the input after each set of at most $k$ edge deletions. The lower-bound construction of Baswana, Choudhary, and Roditty [BCR18], adapted to strong connectivity in [CC20], gives the previous best bound of $Ω(2^kN)$ necessary edges. Hoppenworth, Saranurak, and Wang [HSW25] prove an $O(k4^kN\log N)$ upper bound, leaving a logarithmic gap for fixed $k$. We close this gap by giving an explicit strongly connected graph on $N=2^d$ vertices with $N-1+(N/2)\log_2N$ edges, every one of which is necessary in a two-failure preserver. Together with the upper bound of [HSW25], this proves that the optimal size in the worst case is $Θ_k(N\log N)$ for every fixed $k\geq2$, whereas it is $Θ(N)$ for $k=1$ [GIP20]. The same graph has a one-failure preserver with at most $3(N-1)$ edges. We also give a randomized algorithm that either returns a spanning subgraph or reports failure. For every fixed $c,\varepsilon>0$, with probability at least $1-N^{-c}$ it returns a correct preserver for $k=2$ with $O(N\log N)$ edges, in $\widetilde O(N^{(ω+3)/2+\varepsilon})$ time and $\widetilde O(N^2)$ space. Here $ω$ is the matrix multiplication exponent over a fixed finite field.

0.18

Minimum blockers and extremal graphs for nonnested matchings

cs.DM math.CO ·2026-09-13 ·Pedro M. M. de Castro
theory similarity 0.60
Abstract · 30 pages, 11 figures, 1 algorithm. Substantially expanded version: new constructions with quadratic excess beyond the proposed extremal boun…

We classify all smallest sets of edge deletions that destroy every nonnested perfect matching in a complete ordered graph. The vertices have a fixed linear order. A perfect matching selects edges that use each vertex exactly once; it is nonnested when no selected edge has both endpoints strictly between those of another. On $2k$ vertices, exactly $k$ deletions are necessary, and we describe all $2^k+k-2$ minimum deletion sets for every $k\ge2$. Allowing a matching to leave vertices unused changes the extremal problem. Barát, Freschi and Tóth proposed that an $n$-vertex ordered graph avoiding a nonnested $k$-edge matching can have at most $(k-1)n$ edges. We construct counterexamples for every $k\ge5$ and $n\ge2k+1$. For $n\ge3k$, our constructions exceed the proposed value by a number of edges proportional to $k^2$, matching the order of the known upper bound on this excess. The classification follows from cuts between consecutive intervals; the larger constructions coordinate deletions at the two ends of the vertex order. The exact extremal value remains open in general.

0.30

New Fault-Tolerant $(α,β)$-Spanners

cs.DS ·2026-10-24 ·Merav Parter, Elizaveta Popova, Elad Tzalik
publishedtheory similarity 0.59
Abstract · SODA '27, abstract shortened for arxiv

We present new constructions of vertex fault-tolerant (VFT) $(α,β)$-spanners with substantially improved size bounds. Given a bound $f$ on the number of vertex faults, an $f$-VFT $(α,β)$-spanner is a subgraph of $G$ that preserves an $(α,β)$-spanner of $G- F$ for every fault set $F \subseteq V$ with $|F| \le f$. Most existing constructions of VFT $(α,β)$-spanners rely on a black-box sampling technique that incurs an exponential blow-up compared to their non-fault-tolerant counterparts. We develop two independent techniques for constructing $f$-VFT $(α,β)$-spanners that improve the dependence on $f$, reducing it to polynomial overhead. For every unweighted graph $G=(V,E)$ on $n$ vertices, stretch parameter $k$, and fault parameter $f$, we show: (i) $f$-VFT $(O_ε(k^ε), O_ε(k))$-spanners with $\tilde{O}(f^{exp(1/ε)}\cdot n^{1+1/k})$ edges for any $ε\in (0,1)$. For any fixed constant $ε$, this introduces a $poly(f)$ overhead compared to the non-faulty constructions of [Ben-Levy and Parter, SODA 2020] and [Chechik and Lifshitz, SODA 2026]. (ii) For any $δ\in (0,1)$, an $f$-VFT $\left(O_δ(\sqrt{k}),O_δ(k) \right)$-spanner of size $\tilde{O}(f^{1+δ} \cdot n^{1+\frac{1}{k}})$. Hence, it incurs a size overhead of only $f^{1+δ}$ compared to the above-mentioned non-faulty analogs. (iii) $f$-VFT $(k,k-1)$ spanner of size $O(k^3 \cdot f \cdot n^{1+\frac{1}{k}})$, nearly matching the lower bound $Ω(f^{1-\frac{1}{k}}n^{1+\frac{1}{k}})$ known for $f$-VFT $(2k-1,0)$ spanners by [Bodwin et al., SODA 2018]. The first result is obtained via a new adaptation of the Baswana--Sen framework to the VFT $(α,β)$ setting. The other two bounds follow from a highly involved analysis of a natural extension of the fault-tolerant greedy spanner.

0.31

The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths

cs.DS ·2026-10-13 ·Hitendra Kumar, Mathieu Mari, R. B. Sandeep
theory similarity 0.59
Abstract · added acknowledgement

Fix a set $S$ of positive integers. An $S$-Hamiltonian cycle is a cyclic ordering of all vertices of a graph such that each consecutive pair is joined by a walk whose length belongs to $S$. We study the complexity of deciding whether an input graph admits such an ordering, together with the corresponding path variants with prescribed or unrestricted endpoints. We complete the complexity classification for undirected graphs. In particular, we prove NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026). For digraphs, all three problems are NP-complete for every fixed finite nonempty $S$ and admit linear-time algorithms when $S$ is cofinite. For other fixed infinite sets $S$, we establish NP-complete and undecidable cases, with undecidability occurring even when $S$ is recursive.

0.23