Vertex connectivity of the nonzero nonunit core of the comaximal graph of ${\mathbb{Z}}_n$

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_1{p}_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)=\frac{\varphi (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.

21 pages, 6 figures