{"id":"52b18e07-2ee2-41f1-9abb-bcedc2696ff3","arxiv_id":"2412.09885","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For n-dimensional hypercubes, the structure fault diameter with Q_m subcubes equals n for n=m+2 and n+1 for n≥m+3, and the Q_1-substructure fault diameter equals n+1 for n≥4.","lead":"This paper introduces structure fault diameter and substructure fault diameter, new measures of how much a network's diameter grows when entire structured chunks fail. It computes these values exactly for hypercube networks, generalizing the classic fault diameter result.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Induction in Lemma 4.4 requires an upper bound for D_sc_f(Q_{n-1};Q_{m-1}) that the stated induction hypothesis does not provide.","rationale":"I read the manuscript in good faith and concentrated on the upper-bound chain, Lemmas 4.1 through 4.4, that supports Theorems 4.6 and 4.7. The lower-bound arguments are plausible, but the central defect is in Lemma 4.4, Case 2.1. The proof must show that the residual graph Q_n^1 - B has diameter at most n-1. The cited Lemma 4.3 cannot supply this: using it with its stated parameter m gives a fault cap one too small for |B|, while using it with parameter m-1 would require the hypothesis D_sc_f(Q_{n-1};Q_{m-1}) ≤ n, which is neither a stated induction hypothesis nor a consequence of the surrounding lemmas with the correct direction. This is an internal missing step rather than a disagreement with external consensus, so it is a legitimate correctness risk. The results may still be repairable, likely through a simultaneous induction on n and m, which is why a conditional acceptance remains the appropriate verdict. My analysis agrees with the reader's identification of this step as the weakest assumption, with the clarification that the deeper problem is the unsupported premise for m-1 rather than merely a one-unit cardinality slip.","tokens_in":14022,"tokens_out":14263,"duration_ms":136034,"concrete_test":"Attempt to derive D_sc_f(Q_{n-1};Q_{m-1}) ≤ n using only Lemma 4.2, Theorem 4.1, and the stated Lemma 4.4 induction hypothesis for fixed m. If no such derivation exists without circularly assuming a version of Lemma 4.4 for smaller m, then Lemma 4.4 Case 2.1 remains unproved. Alternatively, reformulate Lemma 4.4 as a simultaneous induction on n+m and check whether the step for (n,m) can supply the needed bound for (n-1,m-1); if that stronger induction goes through, the concern is settled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 4.4, Case 2.1, after routing u-v through Q_n^1, the residual faults are the intersections B of crossing Q_m-faults with Q_n^1; each such intersection is a Q_{m-1}-subcube, and |B| ≤ n-m-2. The proof invokes Lemma 4.3 to conclude D(Q_n^1 - B) ≤ n-1. Both ways of making this invocation explicit fail. If Lemma 4.3 is used with parameter m, its cardinality cap is n-m-3, one less than the bound on |B|. If Lemma 4.3 is used with parameter m-1, the cap matches, but the hypothesis becomes D_sc_f(Q_{n-1};Q_{m-1}) ≤ n, which is not available: the induction hypothesis of Lemma 4.4 is stated only for the fixed m (D_sc_f(Q_k;Q_m) ≤ k+1 for m+3 ≤ k ≤ n-1), and Lemma 4.5 gives the lower bound D_sc_f(Q_{n-1};Q_{m-1}) ≥ n, i.e., the wrong direction. The proof therefore does not establish the required diameter bound in the crossing-fault case. This is load-bearing because Theorem 4.6 and Theorem 4.7 both depend on Lemma 4.4 for their upper bounds; without a repair, the exact stated values are not proven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14289,"tokens_out":19488,"duration_ms":167532,"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":[{"comment":"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.","section":"Section 4, Lemma 4.4, Case 2.1"},{"comment":"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.","section":"Section 4, Lemma 4.3, Case 1.1"},{"comment":"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.","section":"Section 4, Lemma 4.2, Cases 1.2 and 2.2"},{"comment":"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.","section":"Section 4, Lemma 4.2, Case 2.3"}],"minor_comments":[{"comment":"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.","section":"Section 3, Theorem 3.2 proof"},{"comment":"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.","section":"Table 1 and throughout Section 4"},{"comment":"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.","section":"Section 3, Lemma 3.5, Case 1"},{"comment":"The abstract states the range 1 ≤ m ≤ n−2, but Theorem 4.7 covers 0 ≤ m ≤ n−2. This inconsistency should be fixed.","section":"Abstract and Theorem 4.7"},{"comment":"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.","section":"Section 1, paragraph 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's central claims are plausible and the lower bounds are convincing, but the upper-bound proofs in Section 4 have a systematic gap: the induction hypotheses are not strong enough for the parameter shift (from m to m−1) that occurs when crossing faults are restricted to one of the two (n−1)-cubes. This is not a mere presentation issue; Lemma 4.4 and Theorem 4.7 are not established. The authors may be able to repair the proofs by strengthening the induction, but the current manuscript does not do so. I also note that the paper relies on Lemma 2.4 from a self-citation [17] for the connectivity value that sets the fault budget; this is legitimate as an external theorem, but the authors should double-check that the budget numbers derived from it are used consistently. The fit with the journal is appropriate for a combinatorics/graph-theory paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The definitions of structure fault diameter and substructure fault diameter are sensible extensions of the classical fault diameter, and the stated values for hypercubes are clean. The lower-bound constructions (Lemma 3.3, Lemma 4.5, Theorem 4.1) are convincing, and the Q1 case (Theorem 3.6) is mostly fine. If the proofs can be repaired, this would be a useful contribution to the fault-tolerance literature.\n\nThe soft spots are in the upper bounds. In Lemma 3.5, Case 1, the proof cites Lemma 2.2 for a bound on D_s^f(Q_{n-1};Q1), but Lemma 2.2 is about the ordinary fault diameter and does not imply that bound; the induction hypothesis would have done the job. That is a mis-citation, not a fatal flaw.\n\nThe real problem is in Lemma 4.4. The induction is only on n with m fixed, but in Cases 1.1 and 2.1 the residual faults after splitting are Q_{m-1}-subcubes, and the proof invokes D_sc_f(Q_{n-1};Q_{m-1}) ≤ n. That statement is not part of the induction hypothesis. The attempted appeal to Lemma 4.3 also fails: using parameter m leaves the cardinality cap one too small, and using parameter m-1 requires exactly the unavailable hypothesis. This is load-bearing for Theorems 4.6 and 4.7. The gap looks repairable—a stronger induction on both n and m, or a separate lemma for crossing faults, may close it—but as written the upper bounds are not established.\n\nThere is also an overclaim: the introduction states D_s^f(Q_n;Q_m)=n+1 for all m≥0, but the paper only proves the subcube variant D_sc_f and the Q1 substructure case. The abstract correctly restricts to Q1, so the introduction should be corrected.\n\nThe results are plausible and likely true, and the authors are working in a well-established framework. I would send this to a serious referee, but with a clear request for major revision: fix the induction in Lemma 4.4, repair the citation in Lemma 3.5, and align the introduction with what is actually proven.","headline":"Natural new parameters and plausible results, but the upper-bound induction has a load-bearing gap that blocks the main theorems as stated.","tokens_in":14856,"tokens_out":6012,"would_cite":false,"duration_ms":52142,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C40","05C12","05C82"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["structure fault diameter","substructure fault diameter","hypercube","structure connectivity","substructure connectivity","fault diameter","subcube fault diameter","Q_m-subcube"],"falsifier":"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.","tokens_in":13792,"feed_emoji":"🧊","tokens_out":18520,"duration_ms":170238,"temperature":0.7,"pith_summary":"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.","feed_headline":"Deleting subcubes from a hypercube raises diameter by at most one","feed_subtitle":"A faulty Q_m-subcube holds 2^m vertices, yet worst-case survivor distance stays n or n+1.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines fault diameter and proves $D_f(Q_n)=n+1$, the classical benchmark that the new results generalize and the content of Lemma 2.2.","marker":"[7]"},{"why":"Proves that $Q_n$ minus at most $n-2$ vertices still has diameter $n$ (Lemma 2.1), used for path-length bounds in the induction.","marker":"[8]"},{"why":"Introduces $W$-structure and $W$-substructure connectivity and gives their values for hypercubes, including $\\kappa^s(Q_n;Q_1)=n-1$, the deletion budget in Theorems 3.2 through 3.6.","marker":"[10]"},{"why":"States the common-neighbor property of hypercubes used in Lemma 2.5 and Corollary 2.6 to control which faulty subcubes can hit both endpoints of a possible detour.","marker":"[14]"},{"why":"Defines $Q_m$-subcube connectivity and proves $\\kappa^{sc}(Q_n;Q_m)=\\kappa(Q_n;Q_m)=n-m$ (Lemma 2.4), fixing the number of $Q_m$-structures that may be removed in the main theorems.","marker":"[17]"}],"fun_headline_variants":["Structure fault diameter of hypercubes: at most one extra hop","Hypercube diameter rises by at most one under subcube faults","Structure faults never stretch hypercube diameter beyond n+1","Worst-case hypercube distance stays n or n+1 after subcube faults"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Structure fault diameter of hypercubes: at most one extra hop","Hypercube diameter rises by at most one under subcube faults","Structure faults never stretch hypercube diameter beyond n+1","Worst-case hypercube distance stays n or n+1 after subcube faults"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000713,"raw_usage":{"total_tokens":3258,"prompt_tokens":1049,"completion_tokens":2209,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":665,"completion_tokens_details":{"reasoning_tokens":2134}},"tokens_in":665,"tokens_out":2209,"duration_ms":16927,"temperature":1.0,"reasoning_tokens":2134,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:37:53.656666+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines fault diameter and proves $D_f(Q_n)=n+1$, the classical benchmark that the new results generalize and the content of Lemma 2.2."},{"cited_title":"Kung, C.-K","cited_arxiv_id":null,"evidence_quote":"Proves that $Q_n$ minus at most $n-2$ vertices still has diameter $n$ (Lemma 2.1), used for path-length bounds in the induction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces $W$-structure and $W$-substructure connectivity and gives their values for hypercubes, including $\\kappa^s(Q_n;Q_1)=n-1$, the deletion budget in Theorems 3.2 through 3.6."},{"cited_title":"Pan, Star fault tolerance of hypercube, Theoretical Computer Science 972 (2023) 114052","cited_arxiv_id":null,"evidence_quote":"States the common-neighbor property of hypercubes used in Lemma 2.5 and Corollary 2.6 to control which faulty subcubes can hit both endpoints of a possible detour."},{"cited_title":"Sabir and J","cited_arxiv_id":null,"evidence_quote":"Defines $Q_m$-subcube connectivity and proves $\\kappa^{sc}(Q_n;Q_m)=\\kappa(Q_n;Q_m)=n-m$ (Lemma 2.4), fixing the number of $Q_m$-structures that may be removed in the main theorems."}],"review_version":1}