Pith. sign in

REVIEW 4 major objections 5 minor 24 references

Structure fault diameter of hypercubes

T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves exact worst-case diameters for hypercubes under structure faults: n when n=m+2, n+1 otherwise, and n+1 for edge substructures.

desk verdict Natural new parameters and plausible results, but the upper-bound induction has a load-bearing gap that blocks the main theorems as stated. read the letter →

arxiv 2412.09885 v3 pith:Y5J7VCOO submitted 2024-12-13 math.CO

Honggang Zhao , Eminjan Sabir , Cheng-Kuan Lin This is my paper · ORCID
classification math.CO MSC 05C4005C1205C82
keywords structurefaultdiametersubstructurehypercubeconnectivitysubcubeQ_m-subcube
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces two new fault-tolerance measures for networks, the $W$-structure fault diameter and the $W$-substructure fault diameter, which ask: after deleting up to one fewer than the connectivity threshold of disjoint copies of a fixed subgraph $W$, what is the largest distance that can remain between two surviving vertices? For the $n$-dimensional hypercube $Q_n$, the paper claims exact answers: deleting $Q_m$-subcube structures leaves diameter $n$ in the border case $n=m+2$ and diameter $n+1$ whenever $n\ge m+3$, and deleting $Q_1$-substructures (single edges or vertices) leaves diameter $n+1$ for $n\ge4$. These results matter because a faulty $Q_m$-subcube contains $2^m$ vertices, yet the worst-case communication delay grows by at most one beyond the fault-free diameter, matching what a single vertex fault already costs.

What carries the argument

The load-bearing construction is the decomposition of $Q_n$ into two copies $Q_n^{0}$ and $Q_n^{1}$ of $Q_{n-1}$ by fixing the last bit, together with the product representation $Q_n=Q_m\times Q_{n-m}$. Faulty $Q_m$-subcubes are split into those contained entirely in one half and those crossing the boundary; a crossing fault becomes a $Q_{m-1}$-subcube inside each half. The proofs propagate diameter bounds from $Q_{n-1}$ to $Q_n$ by routing paths through the half that is less damaged, using a lemma that guarantees, for any pair of symmetric surviving vertices, a dimension in which both of their neighbors survive. The named quantities $D_f(G;W)$ and $D_f^s(G;W)$ are the new invariants: maximum diameter after removing up to $\kappa(G;W)-1$ vertex-disjoint copies of $W$, or connected subgraphs of $W$, respectively.

What would settle it

For small $n$, exhaustively enumerate every set of up to $\kappa(Q_n;Q_m)-1=n-m-1$ vertex-disjoint $Q_m$-subcubes and compute the maximum distance between surviving vertices; in particular, for $n=5$, $m=2$, every deletion of two vertex-disjoint $Q_2$-subcubes should leave all pairs at distance at most 6, so any surviving pair at distance 7 would disprove the claimed $D^{sc}_f(Q_5;Q_2)=6$ and, with it, Theorem 4.6.

Watch

Extended reading notes

Core claim

The central claim is that structure faults are no worse than vertex faults for hypercube diameters. Formally, the paper proves $D_f(Q_n;Q_m)=n$ when $n=m+2$, and $D_f(Q_n;Q_m)=n+1$ when $n\ge m+3$, while $D_f^s(Q_n;Q_1)=D_f(Q_n;Q_1)=3$ for $Q_3$ and $D_f^s(Q_n;Q_1)=D_f(Q_n;Q_1)=n+1$ for $n\ge4$. The equality $D_f(Q_n;Q_m)=n$ means that deleting the one permitted $Q_{n-2}$-subcube does not stretch distances at all; the equality $n+1$ in the remaining range means the worst-case distance increases by exactly one, the same increase caused by ordinary vertex faults. The paper reaches these values by first establishing the auxiliary $Q_m$-subcube fault diameter $D^{sc}_f(Q_n;Q_m)=m+2$ for $n=m+2$ and $=n+1$ for $n\ge m+3$, and then using $D_f\le D^{sc}_f$ together with matching lower-bound constructions.

Load-bearing premise

The upper-bound argument assumes Lemma 4.3, stated for at most $n-m-3$ faults, applies in Lemma 4.4, Case 2.1, where a set of $n-m-2$ crossing faults has shrunk to $Q_{m-1}$-subcubes, and the text supplies no bridge for this one-unit gap.

Editorial extensions

If this is right

  • For $W=K_1$, the structure fault diameter reduces to the classical fault diameter, so $D_f(Q_n;K_1)=n+1$ recovers the known hypercube fault diameter as a special case.
  • A single deleted $Q_{n-2}$-subcube leaves $Q_n$ with diameter $n$, meaning one permitted structure fault can be exponentially large in vertex count without increasing worst-case distance.
  • For $m\le n-3$, deleting up to $n-m-1$ disjoint $Q_m$-subcubes leaves diameter exactly $n+1$, identical to the bound for deleting up to $n-1$ isolated vertices.
  • For substructure faults of a single edge or vertex, the diameter is $n+1$ for all $n\ge4$, and $3$ for $Q_3$.
  • The auxiliary subcube fault diameter $D^{sc}_f(Q_n;Q_m)$ is itself exactly $n+1$ for $n\ge m+3$ and $m+2$ for $n=m+2$, so every intermediate invariant used in the proof has a complete value.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step, not taken here, is to determine $D_f^s(Q_n;Q_m)$ for $m>1$; the definitions give the immediate lower bound $D_f^s\ge D_f=n+1$, and the paper's induction pattern suggests equality, but the present text proves it only for $m=1$.
  • If the same split-and-transfer argument extends to other Cartesian-product networks, product-structure faults would never cost more than one diameter unit, so designers could equate whole-module failures with single-node failures when budgeting worst-case latency.
  • The worst-case constructions in Lemma 4.5 delete all $Q_m$-subcubes adjacent to a fixed $Q_m$ in one half, forcing any surviving path to cross the half's boundary; a similar construction may give exact lower bounds for other structured fault models in hypercube variants.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper introduces two new graph parameters, the structure fault diameter D_f(G;W) and the substructure fault diameter D_s_f(G;W), defined as the maximum diameter of G after removing up to κ(G;W)−1 W-structures or κ^s(G;W)−1 W-substructures, respectively. For the n-dimensional hypercube Q_n, it claims D_f(Q_n;Q_m)=n for n=m+2 and D_f(Q_n;Q_m)=n+1 for n≥m+3, together with D_s_f(Q_n;Q_1)=n+1 for n≥4 (and D_s_f(Q_3;Q_1)=3). The proofs use induction on n by splitting Q_n into two (n−1)-cubes and routing paths through one half after accounting for crossing faults. The main results are Theorems 3.6, 4.6, and 4.7.

Significance. If the results are correct, the paper extends the classical fault diameter of hypercubes to structure- and substructure-based fault models, giving exact worst-case diameters after removing Q_m-subcubes or Q_1-substructures. The definitions are natural and the lower-bound constructions in Lemmas 3.3 and 4.5 are clean and convincing. The paper does not provide machine-checked proofs or code. However, several load-bearing upper-bound arguments in Section 4 contain gaps in the induction step, and until those are repaired the exact claimed values are not established.

major comments (4)
  1. [Section 4, Lemma 4.4, Case 2.1] The induction hypothesis is stated only for the fixed parameter m, giving D_sc_f(Q_k;Q_m) ≤ k+1 for m+3 ≤ k ≤ n−1. In Case 2.1 the proof invokes D_sc_f(Q_{n−1};Q_{m−1}) ≤ n, which is not part of this hypothesis. Moreover, applying Lemma 4.3 to the residual fault set B_n^m (a set of Q_{m-1}-subcubes in Q_n^1) fails in both possible parameter choices: with parameter m, the cardinality cap in Lemma 4.3 is n−m−3 while |B_n^m| ≤ n−m−2; with parameter m−1, the required condition D_sc_f(Q_{n−1};Q_{m−1}) ≤ n is exactly the unavailable statement. Thus the upper bound D_sc_f(Q_n;Q_m) ≤ n+1 is not proven by the text.
  2. [Section 4, Lemma 4.3, Case 1.1] The induction hypothesis in Lemma 4.3 is for the fixed parameter m, namely D(Q_{k−1}−F_m^{k−1}) ≤ k−1 for m+4 ≤ k ≤ n−1. In Case 1.1 the proof instead uses D(Q_{n−2}−F_{m−1}^{n−2}) ≤ n−2, decreasing the substructure dimension to m−1. The residual faults B_m^{n−1} in Q_{n−1}^1 are intersections of crossing Q_m-subcubes and are Q_{m−1}-subcubes, so the stated induction hypothesis does not apply to them. This makes Lemma 4.3 unproven, and since Lemma 4.4 depends on it, the gap propagates to the main theorems.
  3. [Section 4, Lemma 4.2, Cases 1.2 and 2.2] In Cases 1.2 and 2.2 the proof bounds a path in Q_{m+3}^0−A_{m,0}−B_m (or in Q_{m+3}^1−B_m) by applying Theorem 4.1, which gives D_sc_f(Q_{m+2};Q_m)=m+2. However, the fault set may contain a single Q_{m−1}-subcube arising from the intersection of a crossing Q_m fault, and Theorem 4.1 only covers faults that are Q_m-subcubes. Thus the inequality l(Ps) ≤ m+2 is not justified for such residual fault sets. A separate argument is needed for single Q_{m−1}-subcube faults.
  4. [Section 4, Lemma 4.2, Case 2.3] Case 2.3 refers to 'Case 1.2' to conclude l(Ps) ≤ m+2 for arbitrary unsymmetric vertices u,v in Q_{m+3}^0. But Case 1.2 was proved only for symmetric u and v (with a path of the form ⟨u,Ps,(v)_{m+3},v⟩). The bound on the distance inside Q^0−A−B between two vertices that are at Hamming distance n−1 in Q^0 does not automatically give a diameter bound for all unsymmetric pairs. The argument needs to be stated for all pairs in the subcube, not only for those arising from symmetric endpoints.
minor comments (5)
  1. [Section 3, Theorem 3.2 proof] There is a typo: 'Bellow' should be 'Below'. Also, the line 'we suppose that |F_0^3| = 0 and |F_1^3| = 1' uses F_0^3, which is not defined in the table; it appears the authors mean to exclude single-vertex (K_1) faults and consider exactly one K_2 fault, but this should be stated clearly.
  2. [Table 1 and throughout Section 4] The symbols F_n^k and F_n^k (bold) are defined in Table 1 but the text does not always clearly distinguish them; this makes it hard to follow which fault sets are subsets of S_k(Q_n) and which are arbitrary subgraphs. For example, in Lemma 4.4 the notation B_n^m appears with F_n^m without an explicit restatement of the distinction.
  3. [Section 3, Lemma 3.5, Case 1] The sentence 'By Lemma 2.2, we have D_s_f(Q_n^0;Q_1) ≤ n' is misleading: Lemma 2.2 gives the vertex fault diameter D_f(Q_{n−1}) = n, and the needed bound is on the diameter of Q_{n−1} after removing at most n−2 faulty vertices, which is exactly that vertex fault diameter. The notation D_s_f is not needed here and obscures the argument.
  4. [Abstract and Theorem 4.7] The abstract states the range 1 ≤ m ≤ n−2, but Theorem 4.7 covers 0 ≤ m ≤ n−2. This inconsistency should be fixed.
  5. [Section 1, paragraph 2] The assertion 'it can be observed from the definitions that D_s_f(G;W) ≥ D_f(G;W)' is not true for arbitrary graphs because κ^s(G;W) can be strictly smaller than κ(G;W), so the fault sets counted by D_s_f are a subset of those counted by D_f. It holds in the specific cases treated here (e.g., Q_1-substructures of Q_n, where the connectivities coincide), but the statement as written is too strong.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the claimed fault-diameter values are not equivalent by construction to their inputs; self-cited connectivity lemmas are independent external theorems.

full rationale

The derivation chain introduces D_f and D_sc_f as new quantities and then proves upper and lower bounds using fault-set constructions and induction. The only self-citations appear in Lemmas 2.1, 2.3, and 2.4, and Lemma 2.4 supplies the Q_m-subcube connectivity value n-m. That value is a published, parameter-free theorem from [17] that does not assume the fault-diameter results; it merely sets the fault budget. Under the review rules, such a citation is independent support and does not constitute circularity. No fitted parameter is renamed as a prediction, no target value is assumed in a definition, and no uniqueness claim is imported to exclude alternatives. The significant issues in the paper are correctness gaps, such as the induction hypothesis mismatch in Lemma 4.4 Case 2.1 and the apparent inequality direction in Theorem 4.6, not cases where a conclusion equals its premise by construction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central results import five prior theorems about hypercube connectivity and fault diameters; no free parameters are fitted. The new fault-diameter definitions are formal definitions, not invented entities. The most load-bearing imported value is κ_sc(Q_n;Q_m)=n−m from [17], coauthored by one of the current authors, which determines how many structures may be removed.

assumptions (6)
  • standard math After removal of n−2 or fewer vertices in Q_n (n≥2), the diameter of the remaining graph is still n (Lemma 2.1, cited to [8]).
    Used in base cases and in bounding diameters inside (n-1)-cubes after vertex deletions.
  • standard math D_f(Q_n) = n+1 for n≥3 (Lemma 2.2, cited to [7]).
    Classic fault diameter result used as an input for vertex-fault cases.
  • standard math κ(Q_n;Q_1)=κ_s(Q_n;Q_1)=n−1 for n≥3 (Lemma 2.3, cited to [10]).
    Sets the number of Q_1-structures that may be removed in Section 3.
  • standard math κ_sc(Q_n;Q_m)=κ(Q_n;Q_m)=n−m for n≥3 and m≤n−2 (Lemma 2.4, cited to [17]).
    Sets the fault budget for Q_m-subcube and Q_m-structure removals; this is the key structural-connectivity input, and [17] shares an author with the present paper.
  • standard math Common-neighbor structure in Q_n: any two vertices have exactly two common neighbors if they have any, and these exist iff they differ in exactly two coordinates (Lemma 2.5, cited to [14]).
    Used in Lemma 3.1 to show faulty subcubes cannot block all neighbors of a pair of symmetric vertices.
  • standard math Standard hypercube properties: Q_n is bipartite, n-regular, n-connected, vertex-transitive and edge-transitive (cited to [9]).
    Used to assume without loss of generality that a fault set lies in a particular half or is a specific edge.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Structure fault diameter of hypercubes." pith.science (2026). https://pith.science/paper/Y5J7VCOO

@misc{pith2026241209885,
  author       = {Pith},
  title        = {Pith review of: Structure fault diameter of hypercubes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y5J7VCOO}},
  note         = {Machine review of arXiv:2412.09885}
}
abstract

Structure connectivity and substructure connectivity are innovative indicators for assessing network reliability and fault tolerance. Similarly, fault diameter evaluates fault tolerance and transmission delays in networks. This paper extends the concept of fault diameter by introducing two new variants: structure fault diameter and substructure fault diameter, derived from structure connectivity and substructure connectivity respectively. For a connected graph $G$ with $W$-structure connectivity $\kappa(G;W)$ or $W$-substructure connectivity $\kappa^s(G;W)$, the $W$-structure fault diameter $D_f(G;W)$ and $W$-substructure fault diameter $D_f^s(G;W)$ are defined as the maximum diameter of any subgraph of $G$ resulting from removing up to $\kappa(G;W)-1$ $W$-structures or $\kappa^s(G;W)-1$ $W$-substructures. For the $n$-dimensional hypercube $Q_n$ with $n \geq 3$ and $1 \leq m \leq n - 2$, we determine both $D_f(Q_n;Q_m)$ and $D_f^s(Q_n;Q_1)$. These findings generalize existing results for the diameter and fault diameter of $Q_n$, providing a broader understanding of the hypercube's structural properties under fault conditions.

Figures

Figures reproduced from arXiv: 2412.09885 by the authors.

Figure 1
Figure 1. The n-dimensional hypercube for n ∈ {1,2,3,4}. max{d(u, v) | u, v ∈ V(G)}. We use ⟨u,Ps , v⟩ to denote the shortest path between u and v in a graph G. And we use Kn to represent the complete graph with n vertices. An n-dimensional hypercube is an undirected graph, Qn, with 2n vertices and 2n−1n edges. Each vertex in Qn can be represented as an n-bit binary string. We use boldface to denote vertices in Qn. For any ve… view at source ↗
Figure 2
Figure 2. Q5 = Q2✷Q3 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. An example of |F n 3 | = 6, |A n 3,0 | = 3, |A n 3,1 | = 1 and |B n 3 | = 2. (Qm,t) of Qn is adjacent to exactly n−m subcubes, namely (Qm,t1), (Qm,t2),...,(Qm,tn−m). Clearly, (Qm,ti) is not adjacent to (Qm,tj) for 1 ≤ i, j ≤ n − m, and (Qm,t) and (Qm,ti) can form a subcube, namely (Qm,t ∗ i ), which is isomorphic to Qm+1 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: An illustration of the proof in Theorem 3.2 [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    L. Ba, Y . Zhang, and H. Zhang, The path-structure connectivity of augmented k-ary n- cubes, The Computer Journal 66 (2023) 3119-3128

    work page 2023

  2. [2]

    Bondy and U

    J. Bondy and U. Murty, Graph Theory with Applications, New York, Springer (2008). 12

    work page 2008

  3. [3]

    Chen, Hamiltonicity of hypercubes with faulty vertices, Information processing letters 116 (2016) 343-346

    X. Chen, Hamiltonicity of hypercubes with faulty vertices, Information processing letters 116 (2016) 343-346

    work page 2016

  4. [4]

    Day and A

    K. Day and A. E. Al-Ayyoub, Fault diameter ofk-ary n-cube networks, IEEE Transactions on Paralleel and Distributed Systems 8 (1997) 903-907

    work page 1997

  5. [5]

    Fu, G.-H

    J.-S. Fu, G.-H. Chen, and D.-R. Duh, Node-disjoint paths and related problems on hierar- chical cubic networks, Networks 40 (2002) 142-154

    work page 2002

  6. [6]

    Harary, Graph Theory, Addison-Wesley, Reading (1969)

    F. Harary, Graph Theory, Addison-Wesley, Reading (1969)

    work page 1969

  7. [7]

    M. S. Krishnamoorthy and B. Krishnamurthy, Fault diameter of interconnection networks, Computers and Mathematics with Applications 13 (1987) 577-582

    work page 1987

  8. [8]

    Kung, C.-K

    T.-L. Kung, C.-K. Lin, T. Liang, L.-Y . Hsu, and and J. J.-M. Tan. Fault diameter of hy- percubes with hybrid node and link faults, Journal of Interconnection Networks 10 (2009) 233-242

    work page 2009

Show all 24 references
  1. [9]

    F. T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hy- percubes, Morgan Kaufmann (1992)

    1992

  2. [10]

    C.-K. Lin, L. Zhang, J. Fan, and D. Wang, Structure connectivity and substructure con- nectivity of hypercubes, Theoretical Computer Science 634 (2018) 97-107

    2018

  3. [11]

    Lv, C.-K

    Y . Lv, C.-K. Lin, J. Fan, and X. Jia, Hamiltonian cycle and path embeddings in 3-ary n- cubes based on K1,3-structure faults, Journal of Parallel and Distributed Computing 120 (2018) 1148-1158

    2018

  4. [12]

    Lv, C.-K

    Y . Lv, C.-K. Lin, and J. Fan, Hamiltonian cycle and path embeddings in k-ary n-cubes based on structure faults, The Computer Journal 60 (2017)159-179

    2017

  5. [13]

    B. Niu, S. Zhou, T. Tian, and Q. Zhang, The wide diameter and fault diameter of ex- changed crossed cube, International Journal of Foundations of Computer Science 35 (2024) 435-451

    2024

  6. [14]

    Pan, Star fault tolerance of hypercube, Theoretical Computer Science 972 (2023) 114052

    K. Pan, Star fault tolerance of hypercube, Theoretical Computer Science 972 (2023) 114052

    2023

  7. [15]

    Qi and X

    H. Qi and X. Zhu, The fault-diameter and wide-diameter of twisted hypercubes, Discrete Applied Mathematics 235 (2018) 154-160

    2018

  8. [16]

    Rouskov and P

    Y . Rouskov and P. K. Srimani, Fault diameter of star graphs, Information Processing Let- ters 48 (1993) 243-251

    1993

  9. [17]

    Sabir and J

    E. Sabir and J. Meng, Fault-tolerant hamiltonicity of hypercubes with faulty subcubes, Information Processing letters 172 (2021) 106160

    2021

  10. [18]

    Sabir, J

    E. Sabir, J. Fan, J. Meng, and B. Cheng, Structure fault-tolerant hamiltonian cycle and path embeddings in bipartite k-ary n-cube networks, IEEE Transactions on Reliability 73 (2024) 257-269. 13

    2024

  11. [19]

    Tsai, Y .-C

    T.-H. Tsai, Y .-C. Chen, and J. J.-M. Tan, Topological properties on the wide and fault diameters of exchanged hypercubes, IEEE Transactions on Paralleel and Distributed Sys- tems 25 (2014) 3317-3327

    2014

  12. [20]

    G. Wang, J. Yu, Y . Zou, J. Fan, and W. Cheng, A new measure of fault-tolerance for network reliability: double-structure connectivity, IEEE Transactions on Networking 32 (2024) 874-889

    2024

  13. [21]

    N. Wang, J. Meng, and Y . Tian, Reliability analyses of regular graphs based on edge- structure connectivity, Discrete Applied Mathematics 356 (2024) 329-342

    2024

  14. [22]

    Y . Yang, X. Hua, and L. Yang, Hyper K1,r and sub- K1,r fault tolerance of star graphs, Discrete Applied Mathematics 339 (2023) 172-177

    2023

  15. [23]

    Zhang, W

    Y . Zhang, W. Fan, Z. Han, Y . Song, and R. Wang, Fault-tolerant routing algorithm based on disjoint paths in 3-ary n-cube networks with structure faults, The Journal of Supercom- puting 77 (2021) 13090-13114

    2021

  16. [24]

    Zhao and S

    L. Zhao and S. Wang, Structure connectivity and substructure connectivity of split-star networks, Discrete Applied Mathematics 341 (2023) 359-371. 14

    2023

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.