arxiv: 2605.01565 · v1 · submitted 2026-05-02 · 🧮 math.CO · cs.DM· math.GR

Recognition: unknown

Vertex connectivity of the nonzero nonunit core of the comaximal graph of mathbb Z_n

Bilal Ahmad Rather

Authors on Pith no claims yet

Pith reviewed 2026-05-09 14:04 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.GR

keywords comaximal graphvertex connectivityChinese Remainder Theoremsquarefree modulusgraph on residue classesnonzero nonunits

0 comments

The pith

The nonzero nonunit subgraph G2 of the comaximal graph on Z_n has vertex connectivity equal to φ(n) divided by (largest prime factor minus one), for squarefree n.

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

The paper studies the induced subgraph G2 on the nonzero nonunits in the comaximal graph of integers modulo n. When n is a product of distinct primes p1 to pm, it represents each element by the set of coordinates that vanish under the Chinese Remainder Theorem. This turns G2 into a weighted blow-up of the graph where vertices are nonempty proper subsets and edges connect disjoint sets. The main result shows that the vertex connectivity κ(G2) equals the product of (pi - 1) from i=1 to m-1, which equals φ(n) over (pm - 1). This establishes that G2 achieves the upper bound for connectivity and that its edge connectivity equals its minimum degree. The work also provides distance formulas, the diameter and radius of G2, and a linear-time computation algorithm given the prime factors of n.

Core claim

For n = p1 p2 ⋯ pm with distinct primes p1 < ⋯ < pm, the graph G2 on nonzero nonunits has κ(G2) = ∏_{i=1}^{m-1} (pi - 1) = φ(n)/(pm - 1). This shows G2 is maximally connected and its edge connectivity agrees with its minimum degree.

What carries the argument

The weighted blow-up of the disjointness graph on nonempty proper subsets of {1,…,m}, where vertices are encoded by their vanishing coordinates via the Chinese Remainder Theorem representation of Z_n.

If this is right

The upper bound on vertex connectivity from prior work is achieved and therefore sharp.
Edge connectivity of G2 equals its minimum degree.
Explicit formulas for distances, diameter, and radius of G2 are obtained.
A linear-time algorithm computes these graph parameters from the prime factorization of n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The approach may generalize to non-squarefree moduli by incorporating powers of primes into the encoding.
These connectivity results could apply to analyzing network structures or algebraic graphs arising in cryptography or coding theory.
The subset disjointness model links this graph to extremal set theory and intersection theorems.

Load-bearing premise

The Chinese Remainder Theorem representation converts the comaximal relation into exact disjointness of vanishing coordinate sets without altering any adjacencies.

What would settle it

Take n=30=2*3*5, construct G2 with 30-1-8=21 vertices, and check whether removing any 1 vertex disconnects it while removing 2 does not, confirming connectivity of 2.

Figures

Figures reproduced from arXiv: 2605.01565 by Bilal Ahmad Rather.

**Figure 1.** Figure 1: Weighted disjointness model for n = 30. 4 Degree profile and local structure This section derives explicit local formulas that are missing in the existing literature. In particular, we identify the unique minimum-degree layer and isolate the exact neighborhood that later becomes a minimum vertex cut. For S ⊆ [m], we write S c = [m] \ S. The next proposition identifies the entire neighborhood of a vertex f… view at source ↗

**Figure 2.** Figure 2: Block diagram for the counting argument in Theorem view at source ↗

**Figure 3.** Figure 3: Weighted disjointness model for n = 210 = 2 · 3 · 5 · 7 view at source ↗

**Figure 4.** Figure 4: For n = 30, the class X{3} is a minimum cut view at source ↗

**Figure 5.** Figure 5: shows the shortest-path patterns from Theorem 6.1. The support-set relation alone determines whether the geodesic length is 1, 2, or 3. Case 1: S ∩ T = ∅ Case 2: S ∩ T ̸= ∅, S ∪ T ̸= [m] Case 3: S ∩ T ̸= ∅, S ∪ T = [m] x ←→ y x ←→ z ←→ y x ←→ u ←→ v ←→ y view at source ↗

**Figure 6.** Figure 6: Flowchart for Algorithm 1. 8 Conclusion and future work We have given a complete solution to Problem 7.2 of Banerjee [2]. For the squarefree modulus n = p1p2 · · · pm, with 2 ≤ p1 < · · · < pm, the induced subgraph G2 of the comaximal graph Γ(Zn) on the nonzero nonunits satisfies κ(G2) = mY−1 i=1 (pi − 1) = ϕ(n) pm − 1 . The proof is based on a support-set model obtained from the Chinese remainder theorem… view at source ↗

read the original abstract

This article settles Problem 7.2 posed by [Banerjee, Special Matrices (2022)] for the induced subgraph $G_2$ of the comaximal graph $\Gamma(\mathbb Z_n)$ when $n$ is squarefree. Let $n=p_1p_2\cdots p_m$ with distinct primes $p_1<\cdots<p_m$, and let $G_2$ be the graph on the nonzero nonunit residue classes modulo $n$. We use Chinese remainder representation of $\mathbb Z_n$, and encodes each vertex by the set of vanishing coordinates. This converts $G_2$ into a weighted blow-up of a disjointness graph on nonempty proper subsets of $\{1,\dots,m\}$. Within this model, we derive exact class sizes, explicit degree formulas, the minimum-degree layer, and a short-path criterion. The main theorem proves the connectivity of $G_{2}$ as $\kappa(G_2)=\prod_{i=1}^{m-1}(p_i-1)=\tfrac{\phi(n)}{p_m-1}$. Consequently, earlier upper bound is sharp, $G_2$ is maximally connected, and its edge connectivity agrees with its minimum degree. We also obtain distance formulas, diameter and radius information, and a linear-time algorithm once the prime factorization is known.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript settles Problem 7.2 of Banerjee (2022) for the induced subgraph G₂ of the comaximal graph Γ(ℤ_n) on the nonzero nonunit residue classes, when n is squarefree. Let n = p₁p₂⋯pₘ with distinct primes p₁ < ⋯ < pₘ. The authors encode vertices via their vanishing coordinates under the Chinese Remainder Theorem isomorphism, converting G₂ into a weighted blow-up of the disjointness graph on the nonempty proper subsets of {1,…,m}. They compute explicit class sizes w(S) = ∏_{i∉S}(p_i−1), degree formulas, the minimum-degree layer, and a short-path criterion. The central theorem establishes the vertex connectivity κ(G₂) = ∏_{i=1}^{m−1}(p_i−1) = φ(n)/(p_m−1). As a consequence the earlier upper bound is shown to be tight, G₂ is maximally connected, and its edge-connectivity equals its minimum degree. The paper also supplies distance formulas, diameter and radius, and a linear-time algorithm once the prime factorization of n is known.

Significance. If the result holds, the paper delivers an exact, closed-form solution to an open connectivity question for a natural induced subgraph of the comaximal graph. The modeling via vanishing sets under CRT is faithful to the comaximal relation and yields parameter-free derivations of all quantities (class sizes, degrees, connectivity). The proof that κ(G₂) equals the minimum degree simultaneously confirms maximal connectivity and equality of vertex and edge connectivity. The additional distance, diameter, radius, and algorithmic results increase the utility of the work. These strengths—machine-checkable combinatorial encoding, explicit formulas without fitted parameters, and resolution of a stated open problem—place the contribution at the level of a standard journal acceptance in combinatorial number theory and graph theory on rings.

minor comments (3)

[Main theorem] In the statement of the main theorem, the identification of the minimum-degree layer (the sets S with |S|=1 and the largest prime index) is used to obtain the connectivity value; a one-sentence reminder of why this layer is indeed the unique minimum-degree class would improve readability for readers who skip the degree-formula derivation.
[Proof of main theorem] The short-path criterion is invoked to bound the connectivity from below; while the argument is direct from the blow-up structure, an explicit reference to the corresponding lemma or proposition number in the text would make the logical flow easier to trace.
[Algorithmic section] The linear-time algorithm is stated to run once the prime factorization is known; a brief complexity remark (e.g., that factorization is assumed given, as is standard) would clarify the scope of the claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, accurate summary of our contributions, and recommendation to accept the manuscript. We are pleased that the combinatorial encoding via vanishing sets under the CRT, the explicit formulas, and the resolution of Problem 7.2 are recognized as strengths.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via standard CRT encoding

full rationale

The paper encodes vertices of G2 via vanishing coordinates under the Chinese Remainder Theorem, yielding a faithful weighted blow-up of the disjointness graph on nonempty proper subsets of {1,...,m}. All subsequent quantities (class sizes w(S), degree formulas, minimum-degree layer, short-path criterion, and the explicit formula for κ(G2)) are derived directly from this representation and elementary graph-theoretic arguments. No parameters are fitted from the target data, no load-bearing self-citations appear, and the connectivity result does not reduce to a definition or prior result by the same authors. The modeling step preserves the comaximal relation exactly, so the derivation chain remains independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the Chinese Remainder Theorem for squarefree n, the definition of the comaximal relation, and standard facts about vertex connectivity in graphs; no free parameters or new entities are introduced.

axioms (2)

standard math Chinese Remainder Theorem: Z_n ≅ product of Z_{p_i} when n is squarefree
Invoked to represent each residue class as an m-tuple and to define vanishing coordinates
domain assumption The comaximal relation on nonzero nonunits is preserved under the coordinate-wise encoding
Required for the blow-up model to be faithful to the original graph

pith-pipeline@v0.9.0 · 5542 in / 1577 out tokens · 48851 ms · 2026-05-09T14:04:58.930556+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references

[1]

Afkhami, Z

M. Afkhami, Z. Barati, and K. Khashyarmanesh, On the signless Laplacian spectrum of the comaximal graphs,Asian-Euro. J. Math.16(04) (2023), Art. No. 2350055

2023
[2]

Banerjee, Laplacian spectrum of comaximal graph of the ringZ n,Spec

S. Banerjee, Laplacian spectrum of comaximal graph of the ringZ n,Spec. Matrices 10(2022) 285–298

2022
[3]

A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

2012
[4]

D. M. Cvetkovi´ c, P. Rowlinson and S. Simi´ c,An Introduction to the Theory of Graph Spectra, London Math. Soc. Stud. Texts 75, Cambridge Univ. Press, Cambridge, 2010

2010
[5]

N. M. M. de Abreu, Old and new results on algebraic connectivity of graphs,Linear Algebra Appl.423(2007) 53–73

2007
[6]

D. S. Dummit and R. M. Foote,Abstract Algebra, 3rd ed., Wiley, Hoboken, NJ, 2004

2004
[7]

Fiedler, Algebraic connectivity of graphs,Czechoslovak Math

M. Fiedler, Algebraic connectivity of graphs,Czechoslovak Math. J.23(1973) 298– 305

1973
[8]

H. R. Maimani, M. Salimi, A. Sattari and S. Yassemi, Comaximal graph of commu- tative rings,J. Algebra319(2008) 1801–1808

2008
[9]

Merris, Laplacian matrices of graphs: a survey,Linear Algebra Appl.197/198 (1994) 143–176

R. Merris, Laplacian matrices of graphs: a survey,Linear Algebra Appl.197/198 (1994) 143–176

1994
[10]

S. M. Moconja and Z. Z. Petrovi´ c, On the structure of comaximal graphs of com- mutative rings with identity,Bull. Aust. Math. Soc.83(2011) 11–21

2011
[11]

Mohar, The Laplacian spectrum of graphs, inGraph Theory, Combinatorics, and Applications, Vol

B. Mohar, The Laplacian spectrum of graphs, inGraph Theory, Combinatorics, and Applications, Vol. 2, Wiley, New York, 1991, pp. 871–898. Exact vertex connectivity ofG 2 21

1991
[12]

B. A. Rather, M. Imran and S. Pirzada, On Sombor index and Sombor eigenvalues of comaximal graphs of commutative rings,J. Algebra Appl.23(06) (2024) 2450115

2024
[13]

B. A. Rather, M. Imran and A. Diene, The linear strand of edge ideals of comaximal graphs of commutative rings,Commun. Algebra52(4) (2024) 1486–1500

2024
[14]

B. A. Rather, M. Aouchiche and M. Imran, On Laplacian eigenvalues of comaximal graphs of commutative rings,Indian J. Pure Appl. Math.55(2024) 310–324

2024
[15]

B. A. Rather, Eigenvalues, quotient matrices, and energy of comaximal graphs over ringZ n,Appl. Algebra Eng. Commun. Comput.(2026),https://doi.org/10.1007/ s00200-026-00737-6

2026
[16]

B. A. Rather, Independent domination polynomial of comaximal graphs of commu- tative rings,Algebra colloquium,33(2) (2026) 243–258

2026
[17]

Samei, On the comaximal graph of a commutative ring,Canad

K. Samei, On the comaximal graph of a commutative ring,Canad. Math. Bull.57 (2014) 413–423

2014
[18]

P. K. Sharma and S. M. Bhatwadekar, A note on graphical representation of rings, J. Algebra176(1995), 124–127

1995
[19]

D. B. West,Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, NJ, 2001

2001