Pith. sign in

REVIEW 1 major objections 3 minor 18 references

Neighbor Connectivity of Undirected Toroidal Meshes

T0 review · 1 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that the neighbor connectivity of every $n$-dimensional undirected toroidal mesh $C(d_1,\dots,d_n)$ with $d_i \ge 3$ is exactly $n$, so it takes $n$ source failures (each also disabling its neighbors) to knock the network…

desk verdict Genuine extension of neighbor connectivity from k-ary n-cubes to unequal-side toroidal meshes, with a solid lower-bound architecture but a patchable gap in the n=2 base case of the main induction. read the letter →

arxiv 2506.14240 v1 pith:5PDMKMAZ submitted 2025-06-17 math.CO

Hui-Ming Huang , Ruichao Niu , Min Xu , Jou-Ming Chang This is my paper · ORCID
classification math.CO MSC 05C40
keywords neighborconnectivityundirectedtoroidalmeshfault-tolerancesurvivalgraphvertexk-aryn-cubedisjointpaths
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

The paper shows that in every $n$-dimensional undirected toroidal mesh $C(d_1,\dots,d_n)$ whose side lengths are all at least $3$, the neighbor connectivity is exactly $n$. Neighbor connectivity extends ordinary vertex connectivity to failures that spread: a chosen set $U$ of source faults also disables every neighbor of a source vertex, and the question is how many sources can be removed while the healthy remainder stays connected. The paper proves the lower bound by establishing the stronger statement that after deleting any $\ell < n$ source vertices and their closed neighborhoods, the survival graph still has connectivity at least $2n-2\ell$. It then supplies the matching upper bound and reports a computer simulation that matches the theoretical value.

What carries the argument

The load-bearing mechanism is dimensional slicing, a counting lemma, and a path-construction lemma. The mesh is sliced along a chosen dimension $c$ into subgraphs $C[0],\dots,C[d_c-1]$, each isomorphic to an $(n-1)$-dimensional toroidal mesh. Lemma 3.3 counts, for two adjacent slices $C[i]$ and $C[j]$, the set $H$ of vertices $v$ in $C[i]$ such that both $v$ and its outer neighbor $v^j$ in $C[j]$ are healthy, and asserts $|H|$ strictly exceeds $h = 2n-2-\ell-\mu_i-\mu_j$, where $\mu_i$ and $\mu_j$ are the numbers of source faults in the two slices. Lemma 3.4 converts that surplus into $h+1$ internally disjoint healthy $(x,y)$-paths between a healthy vertex in $C[i]$ and one in $C[j]$, and Theorem 3.5 assembles these across slices to prove $\kappa(C \ominus U) \ge 2n-2\ell$.

What would settle it

On a small mesh such as $C(3,3,3)$, enumerate every set $U$ of $\ell = 2$ source vertices and check Lemma 3.3 directly: if any adjacent pair of slices has $|H| \le h$, the lemma fails and the lower-bound argument collapses. A more direct test is to compute the true vertex connectivity of $C(3,3,3) \ominus U$ for every $U$ of size less than $3$ and look for any survival graph with connectivity below $2n-2\ell$; such a graph would be a counterexample to Theorem 3.5 and hence to $\kappa_{NB} = n$.

Watch

Extended reading notes

Core claim

The central claim is the equality $\kappa_{NB}(C(d_1,d_2,\dots,d_n)) = n$ for all $n \ge 2$ and all $d_i \ge 3$, where $\kappa_{NB}$ is the minimum size of a set $U$ whose closed-neighborhood deletion leaves a disconnected, complete, or empty graph. The proof is carried out through a stronger conditional bound: for every set $U$ of $\ell$ faulty source vertices with $\ell \le n$, the survival graph $C \ominus U$ has vertex connectivity at least $2n - 2\ell$. The argument inducts on dimension, slicing the mesh along one dimension into $d_c$ copies of an $(n-1)$-dimensional toroidal mesh, routing disjoint healthy paths through adjacent slices, and using the induction hypothesis to handle each slice's interior.

Load-bearing premise

The proof collapses if Lemma 3.3's count is wrong: it needs, for any two adjacent slices, strictly more than $h = 2n-2-\ell-\mu_i-\mu_j$ vertices whose outer neighbor is also healthy, and that count drives the construction of every disjoint path in the induction.

Editorial extensions

If this is right

  • Because $\kappa_{NB} = n$, an $n$-dimensional toroidal mesh with side lengths at least $3$ survives any set of $n-1$ spreading-fault sources without its healthy part becoming disconnected, empty, or complete.
  • The stronger bound $\kappa(C \ominus U) \ge 2n-2\ell$ quantifies how connectivity degrades: each additional source fault costs the survival graph $2$ in connectivity until two fault sources would already force a bound of $2$.
  • The result generalizes the known neighbor-connectivity values for $k$-ary $n$-cubes and hypercubes, which are the equal-side-length special cases of toroidal meshes.
  • For fault-tolerant design, the message is that the dimension $n$, not the side lengths $d_i$, is the parameter that determines resilience to cascading neighbor failures.

Reading between the lines

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

  • One could test whether the formula survives when some side length $d_i = 2$, where the paired-outer-neighbor structure used in Lemma 3.3 changes; the counting inequality may fail and the true value could drop below $n$.
  • Because the proof's core is a counting surplus in pairs of adjacent slices, the same technique might yield dimension-dependent neighbor-connectivity formulas for other Cartesian products of cycles, such as partial toroidal meshes with boundary conditions.
  • The reported simulation could be extended to directly verify Lemma 3.3's strict inequality on small meshes, such as $C(3,3,3)$ with all two-fault configurations, which would localize whether the counting bound is ever tight.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 3 minor

Summary. The paper studies the neighbor connectivity κ_NB of the undirected toroidal mesh C(d1,d2,...,dn), where a set U of faulty source vertices removes the closed neighborhood N[U] and the survival graph G⊖U must be disconnected, complete, or empty. The main claim is that κ_NB(C(d1,...,dn)) = n for all n ≥ 2 and d_i ≥ 3. The lower bound is proved through a nested induction: Theorem 3.5 asserts that for any |U| = ℓ ≤ n, the survival graph satisfies κ(C⊖U) ≥ 2n - 2ℓ; Theorem 3.6 then converts this into κ_NB ≥ n. The proof decomposes the mesh into (n-1)-dimensional subnetworks, uses a Menger-type lemma (Lemma 2.4), and relies on prior results of Park and of Dvořák and Gu. The upper bound, together with a corroborating simulation, appears in the later sections.

Significance. If the theorem is correct, it provides an exact, clean formula for the neighbor connectivity of all undirected toroidal meshes, generalizing the known result for the k-ary n-cube. The lower-bound proof is a substantial piece of case analysis: Lemma 3.1 pins down common-neighbor counts, Lemma 3.2 guarantees healthy vertices in every layer, Lemma 3.3 supplies the counting bound |H| > h, and Lemma 3.4 constructs internally disjoint paths. The manuscript makes appropriate use of standard tools (Menger's theorem and cited prior work) and does not appear to define the target parameter in terms of fitted values. The simulation is explicitly corroborative and does not fix any constants in the proof. These are genuine strengths.

major comments (1)
  1. [Theorem 3.5, base case n = 2] The base case of the induction is not established. The proof states that after removing vertex 00 and its neighbors, the graph is 'neither empty nor complete, and it is connected', and concludes that κ(C⊖U) ≥ 2. For classical vertex connectivity this conclusion does not follow: connectedness gives only κ ≥ 1, and the graph being neither complete nor empty is irrelevant to whether a single vertex deletion disconnects the graph. This gap is load-bearing because the induction step for n = k + 1 applies Lemma 3.4 to (k-dimensional) subnetworks; when k = 2 and µ_i = 1, Lemma 3.4 requires κ(C[i]⊖U_i) ≥ 2n - 2 - 2µ_i = 2. The base case must therefore prove that the survival graph is 2-connected, not merely connected. The authors should supply a rigorous argument for this 2-connectivity (for example, an explicit case analysis over d1, d2, or a citation to a known 2-connectedness result for this deletion).
minor comments (3)
  1. [Lemma 3.1] In Case 1.1 the text reads 'One the other hand'; this should be 'On the other hand'.
  2. [Throughout] The notation 'κN B' and 'κN B(C)' is awkwardly spaced; the subscript should be formatted consistently, e.g., κ_NB.
  3. [Theorem 3.6] The assertion that the toroidal mesh is K4-free is used to conclude that the survival graph is never complete; a short justification or reference would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation chain is self-contained and rests on standard Menger-style facts and prior external results.

full rationale

The paper's derivation chain is not circular. The lower-bound proof proceeds through Lemma 3.3 (a counting estimate), Lemma 3.4 (construction of internally disjoint healthy paths), and Theorem 3.5 (an induction on dimension), ultimately yielding Theorem 3.6. The quantitative engine, Lemma 3.3, is derived from Lemma 2.2 (degree counts) and Lemma 3.1 (common-neighbor bounds), not from the target value n or from a fitted parameter. Lemma 3.4 invokes Lemma 2.4, which is a standard Menger-type fan lemma credited to Dvorak and Gu [5], and Lemma 2.3, the connectivity of toroidal meshes credited to Park [17]; both are prior external results rather than self-citations carrying the argument. The final lower bound Theorem 3.6 combines Theorem 3.5 with the K4-freeness of the toroidal mesh to exclude complete survival graphs, and nothing in this step defines the target parameter in terms of itself. The computer simulation is corroborative and is not used to set constants or to replace a proof step. There is no self-citation chain that forces the conclusion, no uniqueness claim imported from the authors' own prior work, and no fitted input renamed as a prediction. The base case n=2 in Theorem 3.5, where connectedness of the survival graph is used to infer κ≥2, is a potential correctness gap since connectedness alone gives only κ≥1; however, that is an invalid inference, not a circular reduction of the theorem to its assumptions. It therefore does not affect the circularity score.

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

No fitted numbers and no new entities are introduced. The proof rests on standard Menger-type fan lemmas, the known connectivity kappa = 2n of toroidal meshes, and the structural fact that the graph is K4-free; all are stated in the cited literature or are immediate from the Cartesian product structure.

assumptions (3)
  • standard math Lemma 2.4 (cited from [5]): in an (f+k)-connected graph, after deleting f vertices, one can route k disjoint paths or an (x,Y)-fan.
    Menger-type tool invoked throughout Section 3 to construct internally disjoint paths in subnetworks.
  • domain assumption Lemma 2.3 (cited from [17]): kappa(C(d1,...,dn)) = 2n for n >= 2 and d_i >= 3.
    Provides the connectivity baseline used in base cases and in fan constructions.
  • domain assumption C(d1,...,dn) is K4-free.
    Used in Theorem 3.6 to assert that survival graphs are not complete graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Neighbor Connectivity of Undirected Toroidal Meshes." pith.science (2026). https://pith.science/paper/5PDMKMAZ

@misc{pith2026250614240,
  author       = {Pith},
  title        = {Pith review of: Neighbor Connectivity of Undirected Toroidal Meshes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5PDMKMAZ}},
  note         = {Machine review of arXiv:2506.14240}
}
abstract

In this paper, we examine the neighbor connectivity, denoted as $\kappa_{NB}$, of the undirected toroidal mesh $C(d_1,d_2,\ldots,d_n)$. We demonstrate that $\kappa_{NB}(C(d_1,d_2,\ldots,d_n)) = n$ for all $n \ge 2$ and $d_i \ge 3$ (for $1 \le i \le n$). Additionally, we perform a computer simulation experiment on neighbor connectivity in undirected toroidal meshes. This experiment not only supports our theoretical findings with empirical results but also provides a deeper understanding of neighbor structure failures in undirected toroidal meshes.

Figures

Figures reproduced from arXiv: 2506.14240 by the authors.

Figure 1
Figure 1. The illustration of undirected toroidal meshes [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The illustration of C[0] in C(3, 3, 2) Hereafter, for convenience, we assume that C(d1, d2, . . . , dn) is partitioned into dc subnetworks, denoted as C[0], C[1], . . . , C[dc − 1], along the c-th dimension. Two different subnetworks C[i] and C[j] are said to be adjacent if and only if |i − j| ≡ 1 (mod dc). For 0 ≤ i < dc, a vertex u = u1u2 · · · uc−1iuc+1 · · · un in C[i] is referred to as u i . By Definition 2.1, … view at source ↗
Figure 3
Figure 3. The distribution of neighbors for a vertex [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (17 more)
Figure 4
Figure 4. Figure 4: The illustration of Case 1.1 in Lemma 3.1. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: The illustration of Case 1.2 in Lemma 3.1. [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: The illustration of Case 2 in Lemma 3.1. [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 7
Figure 7. Figure 7: The illustration for x j ∈ N(Uj ) in Lemma 3.3. Based on the above discussion, x has at least (2n − 2) − 2µi − 2µj neighbors in C[i], denoted as x1, x2, . . . , x2(n−µi−µj−1), that satisfy the following condition: xk ∈/ N[Ui ] and x j k ∈/ N[Uj ] for k ∈ {1, 2, . . . ,…
Figure 8
Figure 8. Figure 8: The illustration for n = 3, |V (C[i])| = 9, and µi + µj = 2 in Lemma 3.3, showing black nodes as faulty vertices, white nodes as healthy vertices, and yellow nodes as healthy vertices in C[i] with corresponding outer neighbors being faulty in C[j]. Below, we prove that…
Figure 9
Figure 9. Figure 9: illustrates these paths. Therefore, {Pk} h+1 k=1 forms h+1 internally disjoint (x, y)-paths passing through only healthy vertices in C[0] and C[1] that connects x and y, and h + 1 = 2n − 2ℓ = m. C[0] C[1] X Y x x1 x1 x2 xh x1 h x1 2 x1 1 y P1 P2 Ph Ph+1 [PITH_FULL_IMA…
Figure 10
Figure 10. Figure 10: The illustration when ℓ = 1, dc = 3, and y = x 1 If y ̸= x 1 , then y 0 ̸= x. If y 0 ∈ X, without loss of generality, let y 0 = xh (i.e., y = x 1 h ) and Y ′ = (Y \{x 1 h })∪{x 1}. Recall that |F1| = 1. By Lemma 2.3, κ(C[1]) = 2(n−1) = h+1 = |Y ′ |+|F1|. According to …
Figure 11
Figure 11. Figure 11: ). C[0] C[1] X Y x x1 x1 x1 P1 1 Ph xh =y Ph+1 0 xh→1 x1 h→1 y=x1 h Ph→1 [PITH_FULL_IMAGE:figures/full_fig_p014_11.png]
Figure 12
Figure 12. Figure 12: The illustration when ℓ = 1, dc = 3 and y ∈ V (C[1]) \ ({x 1} ∪ Y ) It remains to consider y 0 ∈/ X ∪ {x} (i.e., y /∈ Y ∪ {x 1}). Recall that |F0| = |F1| = 1. Let X′ = X \ {xh}. By Lemma 2.3, κ(C[0]) = 2(n − 1) = h + 1 = (|X′ | + 1) + |F0|. According to Lemma 2.4, the…
Figure 13
Figure 13. Figure 13: A 2-dimensional undirected toroidal mesh after removing vertex 00 and its neighbors. [PITH_FULL_IMAGE:figures/full_fig_p015_13.png]
Figure 14
Figure 14. Figure 14: The illustration of three descriptions of paths in Case 2 of Theorem 3.5. [PITH_FULL_IMAGE:figures/full_fig_p017_14.png]
Figure 15
Figure 15. Figure 15: The illustration of Case 2.1, in the condition where [PITH_FULL_IMAGE:figures/full_fig_p017_15.png]
Figure 16
Figure 16. Figure 16: The illustration of Case 2.2 3.2 Upper bound of κNB(C(d1, d2, . . . , dn)) The following theorem provides an example to determine the upper bound of neighbor connec￾tivity in an n-dimensional undirected toroidal mesh. Theorem 3.7. Let C = C(d1, d2, . . . , dn), where …
Figure 17
Figure 17. Figure 17: The illustration of v, N(v) and U As we mentioned in Section 2, the k-ary n-cube Qk n is a special case of the undirected toroidal mesh C(d1, d2, . . . , dn), where di = k for all 1 ≤ i ≤ n. Therefore, we can derive a corollary regarding the neighbor connectivity of Q…
Figure 18
Figure 18. Figure 18: The distribution of the fault experiment on undirected toroidal mesh [PITH_FULL_IMAGE:figures/full_fig_p021_18.png]
Figure 19
Figure 19. Figure 19: The distribution of the fault experiment on [PITH_FULL_IMAGE:figures/full_fig_p021_19.png]
Figure 20
Figure 20. Figure 20: The distribution of the fault experiment on [PITH_FULL_IMAGE:figures/full_fig_p022_20.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Neighbor connectivity of the alternating group graph

    Abdallah, M., Hung, C.-N., 2021. Neighbor connectivity of the alternating group graph. Jour- nal of Interconnection Networks 21 (3), 2150014

    work page 2021

  2. [2]

    N., Agrawal, D

    Bhuyan, L. N., Agrawal, D. P., 1984. Generalized hypercube and hyperbus structures for a computer network. IEEE Transactions on computers 100 (4), 323–333

    work page 1984

  3. [3]

    L., 2006

    Doty, L. L., 2006. A new bound for neighbor-connectivity of abelian cayley graphs. Discrete mathematics 306 (13), 1301–1316

    work page 2006

  4. [4]

    L., Goldstone, R

    Doty, L. L., Goldstone, R. J., Suffel, C. L., 1996. Cayley graphs with neighbor connectivity one. SIAM Journal on Discrete Mathematics 9 (4), 625–642

    work page 1996

  5. [5]

    Neighbor connectivity ofk-ary n-cubes

    Dvoˇ r´ ak, T., Gu, M.-M., 2020. Neighbor connectivity ofk-ary n-cubes. Applied Mathematics and Computation 379, 125237

    work page 2020

  6. [6]

    Neighbor connectivity of pancake graphs and burnt pancake graphs

    Gu, M.-M., Chang, J.-M., 2023. Neighbor connectivity of pancake graphs and burnt pancake graphs. Discrete Applied Mathematics 324, 46–57

    work page 2023

  7. [7]

    Subversion analyses of hierarchical networks based on (edge) neighbor connectivity

    Gu, M.-M., Pai, K.-J., Chang, J.-M., 2023. Subversion analyses of hierarchical networks based on (edge) neighbor connectivity. Journal of Parallel and Distributed Computing 171, 54–65

    work page 2023

  8. [8]

    Neighbour-connectivity in regular graphs

    Gunther, G., 1985. Neighbour-connectivity in regular graphs. Discrete Applied Mathematics 11 (3), 233–243. 22

    work page 1985

Show all 18 references
  1. [9]

    L., 1978

    Gunther, G., Hartnell, B. L., 1978. On minimizing the effects of betrayals in a resistance movement. In: Proc. Eighth Manitoba Conference on Numerical Mathematics and Computing. pp. 285–306

    1978

  2. [10]

    L., 1980

    Gunther, G., Hartnell, B. L., 1980. Optimal k-secure graphs. Discrete Applied Mathematics 2 (3), 225–231

    1980

  3. [11]

    L., 1991

    Gunther, G., Hartnell, B. L., 1991. On m-connected and k-neighbour-connected graphs. Graph Theory, Combinatorics, and Applications 2, 585–596

    1991

  4. [12]

    L., Nowakowski, R., 1987

    Gunther, G., Hartnell, B. L., Nowakowski, R., 1987. Neighbor-connected graphs and projective planes. Networks An International Journal 17 (2), 241–247

    1987

  5. [13]

    S.-T., Ciou, H.-C., Lin, M.-J., 2025

    Juan, J. S.-T., Ciou, H.-C., Lin, M.-J., 2025. The one-fault dimension-balanced hamiltonian problem in toroidal mesh graphs. Symmetry 17 (1), 93

    2025

  6. [14]

    On the neighborhood-connectivity of locally twisted cube networks

    Kung, T.-L., Lin, C.-K., Hung, C.-N., 2022. On the neighborhood-connectivity of locally twisted cube networks. In: Innovative Mobile and Internet Services in Ubiquitous Computing: Proceedings of the 15th International Conference on Innovative Mobile and Internet Services in Ub...

    2022

  7. [15]

    Two-disjoint-cycle-cover vertex bipancyclicity of the bipartite generalized hypercube

    Niu, R.-C., Xu, M., Lai, H.-J., 2021. Two-disjoint-cycle-cover vertex bipancyclicity of the bipartite generalized hypercube. Applied Mathematics and Computation 400, 126090

    2021

  8. [16]

    Queue layouts of toroidal grids

    Pai, K.-J., Chang, J.-M., Wang, Y.-L., Wu, R.-Y., 2014. Queue layouts of toroidal grids. IEICE Transactions on Fundamental of Electronics, Communications and Computer Sciences E97-A (6), 1180–1186

    2014

  9. [17]

    Torus-like graphs and their paired many-to-many disjoint path covers

    Park, J.-H., 2021. Torus-like graphs and their paired many-to-many disjoint path covers. Discrete Applied Mathematics 289, 64–77

    2021

  10. [18]

    Neighbor connectivity of two kinds of cayley graphs

    Shang, Y.-j., Hao, R.-x., Gu, M.-M., 2018. Neighbor connectivity of two kinds of cayley graphs. Acta Mathematicae Applicatae Sinica, English Series 34 (2), 386–397. 23

    2018

Pith tools

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