A study of upper ideal relation graphs of rings

Abstract

Let R be a ring with unity. The upper ideal relation graph ${\Gamma }_U(R)$ of the ring R is the simple undirected graph whose vertex set is the set of all non-unit elements of R and two distinct vertices x, y are adjacent if and only if there exists a non-unit element $z\in R$ such that the ideals (x) and (y) contained in the ideal (z). In this article, we obtain the girth, minimum degree and the independence number of ${\Gamma }_U(R)$. We obtain a necessary and sufficient condition on R, in terms of the cardinality of their principal ideals, such that the graph ${\Gamma }_U(R)$ is planar and outerplanar, respectively. For a non-local commutative ring $R\cong R_1\times R_2\times \cdots \times R_n$, where R_i is a local ring with maximal ideal ${\mathcal{M}}_i$ and $n\ge 3$, we prove that the graph ${\Gamma }_U(R)$ is perfect if and only if $n\in \{3,4\}$ and each ${\mathcal{M}}_i$ is a principal ideal. We also discuss all the finite rings R such that the graph ${\Gamma }_U(R)$ is Eulerian. Moreover, we obtain the metric dimension and strong metric dimension of ${\Gamma }_U(R)$, when R is a reduced ring. Finally, we determine the vertex connectivity, automorphism group, Laplacian and the normalized Laplacian spectrum of ${\Gamma }_U({\mathbb{Z}}_n)$. We classify all the values of n for which the graph ${\Gamma }_U({\mathbb{Z}}_n)$ is Hamiltonian.

Keywords:

• Upper ideal relation graph
• principal ideals
• maximal ideals
• metric dimension
• strong metric dimension

2010 MATHEMATICS SUBJECT CLASSIFICATION:

• 05C25
• 05C50

1 Introduction

The study of graphs associated with algebraic structures has become an exciting research discipline in the past few decades. Subsequently, many researchers have investigated various graphs associated to rings including the zero divisor graph [6], total graph [5], unit graph [8], annihilator graph [12] and co-maximal graph [28]. A fundamental question arises, how do the graphs represent rings and vice versa. In an attempt to answer such questions, Beck [11] initiated the study of zero divisor graph of a commutative ring with unity. Many researchers have investigated various properties including connectedness, completeness, girth, planarity, clique number, independence number, minimum degree etc., of certain graphs associated to rings in [1, 2, 4, 7, 8, 10, 12, 24, 43]. Harary and Melter [23] first explored the problem of finding the metric dimension of a graph. Its applications lie in combinatorial optimization, robot navigation, network verification etc. (see [22, 39]). Determining the metric dimension and strong metric dimension of a graph is an NP-complete problem. The metric dimension and strong metric dimension of graphs associated with rings have been extensively studied in [19–21, 30, 32, 34, 41]. The zero divisor graph of the ring ${\mathbb{Z}}_{p^t}$ has been studied by Pirzada et al. [33]. Smith et al. [40] investigated the perfectness of the zero divisor graph of the ring ${\mathbb{Z}}_n$. Su et al. [42] classified the values of n for which the zero divisor graph of ${\mathbb{Z}}_n$ is of genus at most 3. Das [18] characterized the value of positive integer n for which the intersection graph of ideals of ${\mathbb{Z}}_n$ is perfect. The spectral graph theory is associated with spectral properties including investigation of characteristic polynomials, eigenvalues, eigenvectors of matrices related with graphs. Recently, Chattopadhyay et al. [15] studied the Laplacian spectrum of the zero divisor graph of the ring ${\mathbb{Z}}_n$. They proved that the zero divisor graph of the ring ${\mathbb{Z}}_{p^l}$ is Laplacian integral for every prime p and a positive integer $l\ge 2$. The work on spectral radius, viz. adjacency spectrum, Laplacian spectrum, signless Laplacian spectrum, normalized spectrum etc., of the zero-divisor graphs of the ring ${\mathbb{Z}}_n$ can be found in [15, 27, 35, 36] and references therein.

It is well known that the ideals play a vital role in the development of ring structures, thus it is interesting to study graphs associated with the ideals of a ring. The graphs associated to ideals, viz. inclusion ideal graphs, intersection ideal graphs, ideal-relation graphs, co-maximal ideal graphs etc., of rings have been studied in [3, 13, 26, 45]. Using the idea of revealing relationships between the ideals and the elements of the ring, Ma et al. [26] introduced the ideal-relation graph of the ring R, denoted by $\overrightarrow{{\Gamma }_i}(R)$, is a directed graph whose vertex set is R and there is an edge from a vertex x to a distinct vertex y if and only if $(x)\subset (y)$. Analogously, the undirected ideal-relation graph of the ring R is the simple graph whose vertex set is R and two distinct vertices x, y are adjacent if and only if either $(x)\subset (y)$ or $(y)\subset (x)$, that is the principal ideals (x) and (y) are comparable in the poset of principal ideals of R. So it is natural to define a new graph on a ring R such that its vertices x and y are adjacent if and only if (x) and (y) have an upper bound in the poset of the principal ideals of R. In view of this, we define upper ideal relation graph associated to the ring R. The upper ideal relation graph ${\Gamma }_U(R)$ of the ring R is the simple undirected graph whose vertex set is the set of all non-unit elements of R and two distinct vertices x, y are adjacent if and only if there exists a non-unit element $z\in R$ such that the ideals (x) and (y) contained in the ideal (z).

In this article, we study the upper ideal relation graph ${\Gamma }_U(R)$ of the ring R. This paper is arranged as follows. In Section 2, we recall necessary definitions and results. Section 3 comprises various results of the graph ${\Gamma }_U(R)$ including completeness, minimum degree, independence number and planarity. In Section 4, for a reduced ring R, we obtain the metric and strong metric dimension of ${\Gamma }_U(R)$. In Section 5, we discuss the perfectness of ${\Gamma }_U(R)$, when $R\cong R_1\times R_2\times \cdots \times R_n$, where $n\ge 2$. In Section 6, we study the upper ideal relation graph the ring ${\mathbb{Z}}_n$ of integers modulo n.

2 Preliminaries

In this section, we recall necessary definitions, results and notations of graph theory from [44]. A graph Γ is a pair $\Gamma =(V,E)$, where $V=V(\Gamma )$ and $E=E(\Gamma )$ are the set of vertices and edges of Γ, respectively. Two distinct vertices $x,y\in \Gamma$ are $\mathit{adjacent}$, denoted by $x\sim y$, if there is an edge between x and y. Otherwise, we denote it by $x\nsim y$. The distance between two vertices x, y in Γ is the number of edges in a shortest path connecting them and it is denoted by d(x, y). The diameter $\mathit{diam}(\Gamma )$ of Γ is the greatest distance between any pair of vertices. The set $N_{\Gamma }(x)$ of all the vertices adjacent to x in Γ is said to be the neighborhood of x. Let ${\Gamma }_1$ and ${\Gamma }_2$ be two graphs. The union, ${\Gamma }_1\cup {\Gamma }_2$, of the graphs ${\Gamma }_1$ and ${\Gamma }_2$ is the graph with $V({\Gamma }_1\cup {\Gamma }_2)=V({\Gamma }_1)\cup V({\Gamma }_2)$ and $E({\Gamma }_1\cup {\Gamma }_2)=E({\Gamma }_1)\cup E({\Gamma }_2)$. The join, ${\Gamma }_1\vee {\Gamma }_2$, of ${\Gamma }_1$ and ${\Gamma }_2$ is the graph obtained from the union of ${\Gamma }_1$ and ${\Gamma }_2$ by adding new edges from each vertex of ${\Gamma }_1$ to every vertex of ${\Gamma }_2$. Let Γ be a graph on k vertices and $V(\Gamma )=\{u_1,u_2,\dots ,u_k\}$. Suppose that ${\Gamma }_1,{\Gamma }_2,\dots ,{\Gamma }_k$ are k pairwise disjoint graphs. Then the generalised join graph, $\Gamma [{\Gamma }_1,{\Gamma }_2,\dots ,{\Gamma }_k]$, of ${\Gamma }_1,{\Gamma }_2,\dots ,{\Gamma }_k$ is the graph formed by replacing each vertex u_i of Γ by Γ_i and then joining each vertex of Γ_i to every vertex of Γ_j whenever $u_i\sim u_j$ in Γ (cf. [38]). A graph Γ is said to be complete if every two distinct vertices are adjacent. The complete graph on n vertices is denoted by K_n. A path P_n in a graph is a sequence of n distinct vertices with the property that each vertex in the sequence is adjacent to the next vertex of it. A cycle is a path that begins and ends on the same vertex. If a cycle is of length n then we write it as C_n. A cycle is said to be Hamiltonian cycle if it covers all the vertices. A graph Γ is said to be Hamiltonian if it contains a Hamiltonian cycle. The girth of Γ is the length of its shortest cycle and is denoted by $g(\Gamma )$. A graph Γ is bipartite if $V(\Gamma )$ is the union of two disjoint independent sets. It is well known that a graph is bipartite if and only if it has no odd cycle [44, Theorem 1.2.18]. A graph Γ is said to be a complete bipartite graph, denoted by $K_{m,n}$ if the vertex set $V(\Gamma )$ can be partitioned into two nonempty sets A of m vertices and B of n vertices such that two distinct vertices are adjacent if and only if they do not belong to the same set.

Theorem 2.1.

[44, Theorem 1.2.26] A connected graph Γ is Eulerian if and only if degree of every vertex is even.

A subset X of $V(\Gamma )$ is said to be independent if no two vertices of X are adjacent. The independence number of Γ is the cardinality of the largest independent set and it is denoted by $\alpha (\Gamma )$. The chromatic number of Γ, denoted by $\chi (\Gamma )$, is the smallest number of colors needed to color the vertices of Γ such that no two adjacent vertices share the same color. A clique in Γ is a set of pairwise adjacent vertices. The clique number of Γ is the size of maximum clique in Γ and it is denoted by $\omega (\Gamma )$. It is well known that $\omega (\Gamma )\le \chi (\Gamma )$ (see [44]). A vertex (edge) cutset in a connected graph Γ is a set of vertices (edges) whose deletion increases the number of connected components of Γ. The vertex connectivity of a connected graph Γ, denoted by $\kappa (\Gamma )$, is the minimum number of vertices whose removal makes Γ disconnected or reduces to a single vertex graph. A graph Γ is outerplanar if it can be embedded in the plane such that all vertices lie on the outer face. A graph Γ is planar if it can be drawn on a plane without edge crossing. It is well known that every outerplanar graph is a planar graph. Now we have the following known results related to outerplanar and planar graphs.

Theorem 2.2.

[44] A graph Γ is outerplanar if and only if it does not contain a subdivision of K₄ or $K_{2,3}$.

Theorem 2.3.

[44] A graph Γ is planar if and only if it does not contain a subdivision of K₅ or $K_{3,3}$.

A graph Γ is perfect if $\omega (\Gamma \prime )=\chi (\Gamma \prime )$ for every induced subgraph $\Gamma \prime$ of Γ. Recall that the complement $\overline{\Gamma }$ of Γ is a graph with same vertex set as Γ and distinct vertices $u,v$ are adjacent in $\overline{\Gamma }$ if they are not adjacent in Γ. A subgraph $\Gamma \prime$ of Γ is called hole if $\Gamma \prime$ is a cycle as an induced subgraph, and $\Gamma \prime$ is called an antihole of Γ if $\overline{\Gamma \prime }$ is a hole in $\overline{\Gamma }$.

Theorem 2.4.

[16] A finite graph Γ is perfect if and only if it does not contain hole or antihole of odd length at least 5.

In a graph Γ, a vertex z resolves a pair of distinct vertices x and y if $d(x,z)\ne d(y,z)$. A resolving set of Γ is a subset $\mathcal{R}\subseteq V(\Gamma )$ such that every pair of distinct vertices of Γ is resolved by some vertex in $\mathcal{R}$. The metric dimension of Γ, denoted by $\beta (\Gamma )$, is the minimum cardinality of a resolving set of Γ. Note that the twin vertices in a graph correspond to vertices sharing same neighbourhood.

Lemma 2.5.

If U is twin-set in a connected graph Γ of order n with $\left|U\right|=l\ge 2$, then every resolving set for Γ contains at least l – 1 vertices of U.

Lemma 2.6.

[14, Theorem 1] For positive integers d and m with d < m, define f(m, d) as the least positive integer k such that $k+d^k\ge m$. Then for a connected graph Γ of order $m\ge 2$ and diameter d, the metric dimension $\beta (\Gamma )\ge f(m,d)$.

For vertices u and v in a graph Γ, we say that z strongly resolves u and v if there exists a shortest path from z to u containing v, or a shortest path from z to v containing u. A subset U of $V(\Gamma )$ is a strong resolving set of Γ if every pair of vertices of Γ is strongly resolved by some vertex of U. The least cardinality of a strong resolving set of Γ is called the strong metric dimension of Γ and is denoted by $\mathrm{sdim}(\Gamma )$. For vertices u and v in a graph Γ, we write $u\equiv v$ if $N[u]=N[v]$. Notice that that $\equiv$ is an equivalence relation on $V(\Gamma )$. We denote by $\widehat{v}$ the $\equiv$-class containing a vertex v of Γ. Consider a graph $\widehat{\Gamma }$ whose vertex set is the set of all $\equiv$-classes, and vertices $\widehat{u}$ and $\widehat{v}$ are adjacent if u and v are adjacent in Γ. This graph is well-defined because in Γ, $w\sim v$ for all $w\in \widehat{u}$ if and only if $u\sim v$. We observe that $\widehat{\Gamma }$ is isomorphic to the subgraph ${\mathcal{R}}_{\Gamma }$ of Γ induced by a set of vertices consisting of exactly one element from each $\equiv$-class.

Theorem 2.7.

[25, Theorem 2.2] For any graph Γ with diameter at most 2, we have $\mathrm{sdim}(\Gamma )=|V(\Gamma )|-\omega (\widehat{\Gamma })$.

Throughout the paper, R is a ring with unity. For basic definitions of ring theory, we refer the reader to [9]. The set of zero-divisors and the set of units of the ring R is denoted by Z(R) and U(R), respectively. The set of all nonzero elements of R is denoted by $R^{*}$. A ring R is called local if it has a unique maximal ideal $\mathcal{M}$ and we abbreviate this by $(R,\mathcal{M})$. In addition, for $x\in R$, (x) denotes the ideal generated by x. An ideal of a ring R is said to be a maximal principal ideal if it is maximal among all the principal ideals of R. The following lemma is useful in the sequel.

Remark 2.8.

For the fields F₁ and F₂, if $R\cong F_1\times F_2$, then we have $${\Gamma }_U(F_1\times F_2)\cong K_1\vee (K_{\left|F_1\right|-1}\cup K_{\left|F_2\right|-1}).$$

3 Invariants of ${\Gamma }_U(R)$

In this section, we study the algebraic properties of R as well as graph theoretic properties of the upper ideal relation graph ${\Gamma }_U(R)$. We obtain the girth, minimum degree, independence number of ${\Gamma }_U(R)$. We obtain a necessary and sufficient condition on R, in terms of the cardinality of their principal ideals, such that the graph ${\Gamma }_U(R)$ is planar and outerplanar, respectively. For $x,y\in V({\Gamma }_U(R))$, we have $x\sim 0\sim y$. It follows that the graph ${\Gamma }_U(R)$ is connected and hence $\mathit{diam}({\Gamma }_U(R))\le 2$. First note that all the elements of the ideal (x) are adjacent in ${\Gamma }_U(R)$. Then one can easily observe that ${\Gamma }_U(R)$ is a star graph if and only if $|(x)|\le 2$ for all $x\in V({\Gamma }_U(R))$. Consequently, ${\Gamma }_U(R)$ contains a cycle if and only if $|(x)|\ge 3$ for some $x\in V({\Gamma }_U(R))$. Moreover, $g({\Gamma }_U(R))\in \{3,\infty \}$.

Further note that, if R has at least two maximal principal ideals $(x_1)$ and $(x_2)$, then $x_1\nsim x_2$ in ${\Gamma }_U(R)$. Consequently, by the definition of ${\Gamma }_U(R)$, we have the following remark.

Remark 3.1.

The upper ideal relation graph ${\Gamma }_U(R)$ is complete if and only if R has a unique maximal principal ideal. In particular, ${\Gamma }_U({\mathbb{Z}}_n)$ is complete if and only if $n=p^{\alpha }$ for some prime p.

Now we investigate the planarity of ${\Gamma }_U(R)$ in the following theorem.

Theorem 3.2.

The upper ideal relation graph ${\Gamma }_U(R)$ is planar if and only if $|(x)|\le 4$ for all non-unit element x of R.

Proof.

Suppose that ${\Gamma }_U(R)$ is a planar graph. If there exists a non-unit element x of R such that $|(x)|\ge 5$, then the elements of (x) induces a complete subgraph which is isomorphic to K₅; a contradiction. Conversely, suppose that $|(x)|\le 4$ for all $x\in R\setminus U(R)$. First let $|(x_1)|=2$ and $|(x_2)|=3$ for some non-unit elements x₁, x₂ of R. Then note that $x_1\nsim x_2$ in ${\Gamma }_U(R)$. Otherwise, there exists a non-unit element $z\in R$ such that $|(z)|\ge 5$, a contradiction. Similarly, if $|(x_1)|\in \{3,4\}$ and $|(x_2)|\in \{3,4\}$, then $x_1\nsim x_2$ in ${\Gamma }_U(R)$. Next, let $(x_1)\ne (x_2)$ and $|(x_1)|=|(x_2)|=2$ for some $x_1,x_2\in R\setminus U(R)$. If $x_1\sim x_2$, then $x_1,x_2\in (x)$ for some $x\in R\setminus U(R)$. By hypothesis, we obtain $|(x)|\le 4$, which is not possible. Therefore, $x_1\nsim x_2$. Thus, ${\Gamma }_U(R)$ is a planar graph. □

Corollary 3.3.

The graph ${\Gamma }_U({\mathbb{Z}}_n)$ is planar if and only if $n=4,6,8,9$ or p.

In similar lines of the proof of Theorem 3.2, we have the following theorem.

Theorem 3.4.

The upper ideal relation graph ${\Gamma }_U(R)$ is outerplanar if and only if $|(x)|\le 3$ for all non-unit element x of R.

Corollary 3.5.

The graph ${\Gamma }_U({\mathbb{Z}}_n)$ is an outerplanar graph if and only if n = 4, 6, 9 or p.

Theorem 3.6.

The minimum degree of the graph ${\Gamma }_U(R)$ is m – 1, where m is the cardinality of smallest maximal principal ideal of the ring R.

Proof.

Let $x\in V({\Gamma }_U(R))$. Then x is contained in some maximal principal ideal (z). Since (z) induces a clique of size $\left|z\right|-1$, we get $\mathrm{deg}(x)\ge \left|z\right|-1$. Let (y) be a maximal principal ideal of the smallest size m. Then $\mathrm{deg}(y)=m-1$. Consequently, $\mathrm{deg}(x)\ge |(z)|-1\ge m-1$. Thus, the minimum degree of ${\Gamma }_U(R)$ is $m - 1$. □

Corollary 3.7.

Let $n=p_1^{n_1}{p}_2^{n_2}{p}_3^{n_3}\cdots p_m^{n_m}$ such that $p_1<p_2<\cdots <p_m$. Then the minimum degree of ${\Gamma }_U({\mathbb{Z}}_n)$ is $\frac{n}{p_m}-1$.

Theorem 3.8.

The independence number of the graph ${\Gamma }_U(R)$ is $|\mathrm{Max}(R)|$, where Max(R) is the set of all maximal principal ideals of the ring R.

Proof.

Note that $(x_1),(x_2)\in \mathrm{Max}(R)$, we get $x_1\nsim x_2$ in ${\Gamma }_U(R)$. It follows that $\alpha ({\Gamma }_U(R))\ge |\mathrm{Max}(R)|$. Let I be an arbitrary independent set of ${\Gamma }_U(R)$ and let $x\in I$. Then $x\in (z)$ for some $(z)\in \mathrm{Max}(R)$. Also the subgraph induced by (z) forms a clique. Consequently, I can not contain any element of (z) other than x. It implies that $\left|I\right|\le |\mathrm{Max}(R)|$. Thus, the result holds. □

Corollary 3.9.

The independence number of ${\Gamma }_U({\mathbb{Z}}_n)$ is the number of distinct prime factors of n.

Define a relation $x\simeq y$ if and only if $(x)=(y)$. It is easy to observe that $\simeq$ is an equivalence relation and $[x]$ is an equivalence class containing x. Note that $V({\Gamma }_U(R))=\underset{x\in R\setminus U(R)}{\cup }[x]$.

Theorem 3.10.

The graph ${\Gamma }_U(R)$ is Eulerian if and only if $\left|R\right|$ and $|R\setminus U(R)|$ is odd.

Proof.

First suppose that ${\Gamma }_U(R)$ is Eulerian. Since 0 is adjacent with every element of ${\Gamma }_U(R)$ we obtain $\mathrm{deg}(0)=|R\setminus U(R)|-1$. By Theorem 2.1, $|R\setminus U(R)|$ is odd. Let (x) be maximal principal ideal of R. Then $\mathrm{deg}(x)=|(x)|-1$. Since ${\Gamma }_U(R)$ is Eulerian, we get $|(x)|$ is odd. Consequently, for any $y\in V({\Gamma }_U(R))$, we get o(y) is always odd in the group $(R,+)$. It follows that $\left|R\right|$ is odd.

Conversely, suppose that $\left|R\right|$ and $|R\setminus U(R)|$ is odd. Clearly, $\mathrm{deg}(0)=|R\setminus U(R)|-1$ which is an even number. Let $x\ne 0\in V({\Gamma }_U(R))$. Then $x\in [y]$ fo some $y\in R\setminus U(R)$. Note that each equivalence class under the relation $\simeq$, defined above, forms a clique. Moreover, if $x_1\sim y_1$, where $x_1\in [z_1]$ and $y_1\in [z_2]$, then $x\prime \sim y\prime$ for each $x\prime \in [z_1]$ and $y\prime \in [z_2]$. Consequently, $\mathrm{deg}(x)=(|[x]|-1)+|[x_1]|+\cdots +|[x_m]|+1$. Since $\left|R\right|$ is odd, each equivalence class of the relation $\simeq$ is of even size. Hence, deg(x) is even and so ${\Gamma }_U(R)$ is Eulerian. □

Theorem 3.11.

Let R be a principal ideal ring having n maximal ideals, ${\mathcal{M}}_1,{\mathcal{M}}_2,\dots ,{\mathcal{M}}_n$ of R such that $\left|{\mathcal{M}}_1\right|\ge \left|{\mathcal{M}}_2\right|\ge \cdots \ge \left|{\mathcal{M}}_n\right|$. Then $\omega ({\Gamma }_U(R))=\left|{\mathcal{M}}_1\right|$.

Proof.

We prove the result by applying induction on n. Let n = 2. Suppose that ${\mathcal{M}}_1,{\mathcal{M}}_2$ are maximal ideals of R with $\left|{\mathcal{M}}_1\right|\ge \left|{\mathcal{M}}_2\right|$. First we cover all the elements of ${\mathcal{M}}_1$ by using $\left|{\mathcal{M}}_1\right|$ colors. Next, if $x\in {\mathcal{M}}_2\setminus {\mathcal{M}}_1$, then these can be colored using the colors used in the coloring of the set ${\mathcal{M}}_1\setminus {\mathcal{M}}_2$ as $|{\mathcal{M}}_2\setminus {\mathcal{M}}_1|\le |{\mathcal{M}}_1\setminus {\mathcal{M}}_2|$. It follows that $\chi ({\Gamma }_U(R))\le \left|{\mathcal{M}}_1\right|$. Also, note that all the elements of ${\mathcal{M}}_1$ forms a clique of size $\left|{\mathcal{M}}_1\right|$. Therefore, $\omega ({\Gamma }_U(R))=\left|{\mathcal{M}}_1\right|$. Now, assume that $n\ge 3$. Clearly, $\omega ({\Gamma }_U(R))\ge \left|{\mathcal{M}}_1\right|$. Let if possible, $\omega ({\Gamma }_U(R))>\left|{\mathcal{M}}_1\right|$. Then there exists a set T of $V({\Gamma }_U(R))$ such that $\left|{\mathcal{M}}_1\right|<\left|T\right|$ and all the elements of T forms a clique. If T contains any element of ${\mathcal{M}}_n\setminus {\cup }_{i=1}^{n-1}{\mathcal{M}}_i$, then $T\subseteq {\mathcal{M}}_n$; a contradiction. Therefore, $T\subseteq {\cup }_{i=1}^{n-1}{\mathcal{M}}_i$. Suppose that $J={\cap }_{i=1}^{n-1}{\mathcal{M}}_i$ so that $J\ne 0$. Further, assume that $\overline{R}=R/J$. Notice that all the elements of $\overline{T}$ forms a clique in $\overline{R}$. Since $\overline{R}$ is a ring with n – 1 maximal ideals, by induction hypothesis, we have $\omega ({\Gamma }_U(\overline{R}))=\left|\overline{{\mathcal{M}}_1}\right|\ge \left|\overline{T}\right|$. It follows that $\left|T\right|\le \left|{\mathcal{M}}_1\right|$; a contradiction. Thus, $\omega ({\Gamma }_U(R))=\left|{\mathcal{M}}_1\right|$. □

Corollary 3.12.

Let $n=p_1^{n_1}{p}_2^{n_2}{p}_3^{n_3}\cdots p_m^{n_m}$ such that $p_1<p_2<\cdots <p_m$. Then $\omega ({\Gamma }_U({\mathbb{Z}}_n))=\frac{n}{p_1}$.

4 Metric dimension and strong metric dimension of ${\Gamma }_U(R)$

In this section, we obtain the metric and the strong metric dimension of ${\Gamma }_U(R)$ for the reduced ring $R\cong F_1\times F_2\times \cdots \times F_n$, where $n\ge 2$. For $i_1,i_2,\dots ,i_k\in [n]$, we define $\widehat{A_{i_1{i}_2\cdots i_k}}=\{(a_1,a_2,\dots ,a_n): \text{only} a_{i_1},a_{i_2},\dots ,a_{i_k}\text{are nonzero}\}$. For instance, if $R\cong F_1\times F_2\times \cdots \times F_5$, then $\widehat{A_{234}}=\{(0,a_2,a_3,a_4,0):a_2\in F_2^{*},a_3\in F_3^{*},a_4\in F_4^{*}\}$. We begin with the following remark.

Remark 4.1.

Let $x=(x_1,x_2,\dots ,x_n)$ and $y=(y_1,y_2,\dots ,y_n)$ in $V({\Gamma }_U(R))$ with $(x)=(y)$. Then x_i = 0 if and only if y_i = 0 for each i.

Lemma 4.2.

Let $R\cong F_1\times F_2\times \cdots \times F_n$ such that $n\ge 3$. Then for $x_1,x_2\in V({\Gamma }_U(R)),(x_1)=(x_2)$ if and only if $N[x_1]=N[x_2]$.

Proof.

First suppose that $(x_1)=(x_2)$. If $x\in N[x_1]$, then there exists a non-unit element $z\in R$ such that $(x)\subseteq (z)$ and $(x_1)\subseteq (z)$. Since $(x_1)=(x_2)$, we get $x\sim x_2$ in ${\Gamma }_U(R)$ and so $x\in N[x_2]$. Thus, $N[x_1]\subseteq N[x_2]$. Similarly, $N[x_2]\subseteq N[x_1]$. To prove the converse, let if possible $(x_1)\ne (x_2)$, where $x_1=(a_1,a_2,\dots ,a_n),x_2=(b_1,b_2,\dots ,b_n)$. Since $(x_1)\ne (x_2)$, by Remark 4.1, there exists $j\in [n]$ such that a_j = 0 but $b_j\ne 0$. Now choose

$z=(z_1,\dots ,z_{j-1},0,z_{j+1},\dots ,z_n)\in V({\Gamma }_U(R))$ such that $z_i\ne 0$ whenever b_i = 0. Note that $x_1\sim z$ but $x_2\nsim z$ in ${\Gamma }_U(R)$. Therefore, $N[x_1]\ne N[x_2]$. Thus, the result holds. □

Define a relation $\equiv$ on $V({\Gamma }_U(R))$ such that $x\equiv y$ if and only if $N[x]=N[y]$. Note that $\equiv$ is an equivalence relation. For $R\cong F_1\times F_2\times \cdots \times F_n$, where $n\ge 3$, note that $V({\Gamma }_U(R))$ has $2^n-1$ equivalence classes, viz. $\widehat{A_0},\widehat{A_{i_1}},\dots ,\widehat{A_{i_1{i}_2\cdots i_{n¯1}}}$. Notice that $\left|\widehat{A_0}\right|=1$ and $\left|\widehat{A_{i_1{i}_2\cdots i_k}}\right|\ge 2$, whenever $F_i\ne {\mathbb{Z}}_2$ for each i.

Theorem 4.3.

Let $R\cong F_1\times F_2\times \cdots \times F_n$, where $n\ge 2$. Then $$\mathrm{sdim}({\Gamma }_U(R))=\{\begin{array}{cc}\left|F_1\right|+\left|F_2\right|-3\hfill & if n=2\hfill \\ |R\setminus U(R)|-2^{n-1}\hfill & n\ge 3\hfill \end{array}$$

Proof.

By Remark 2.8, we have ${\Gamma }_U(F_1\times F_2)=K_1\vee (K_{\left|F_1\right|-1}\cup K_{\left|F_2\right|-1})$. Notice that the reduced graph ${\mathcal{R}}_{{\Gamma }_U(R)}$ is isomorphic to a path graph on three vertices. Therefore, $\omega ({\mathcal{R}}_{{\Gamma }_U(R)})=2$. By Theorem 2.7, we get $\mathrm{sdim}({\Gamma }_U(F_1\times F_2))=\left|F_1\right|+\left|F_2\right|-3$. Next, we assume that $R\cong F_1\times F_2\times \cdots \times F_n$ such that $n\ge 3$. First suppose that n is odd. Note that the set $$\begin{array}{c}\mathcal{C}=\widehat{A_0}\cup \left(\underset{\stackrel{i_1\in \left[n\right]}{}}{\cup }\widehat{A_{i_1}}\right)\cup \left(\underset{\stackrel{i_1,i_2\in \left[n\right]}{}}{\cup }\widehat{A_{i_1{i}_2}}\right)\\ \hspace{1em}\cup \cdots \cup \left(\underset{\stackrel{i_r\in \left[n\right]}{1\le r\le \lfloor \frac{n}{2}\rfloor }}{\cup }\widehat{A_{i_1{i}_2\cdots i_{\lfloor \frac{n}{2}\rfloor }}}\right)\end{array}$$forms a clique in ${\Gamma }_U(R)$. To determine the strong metric dimension of ${\Gamma }_U(R)$, we need to find $\omega ({\mathcal{R}}_{{\Gamma }_U(R)})$. Further, by considering exactly one representative of each equivalence class from $\mathcal{C}$, we obtain $\omega ({\mathcal{R}}_{{\Gamma }_U(R)}){\ge }^n{C}_0{+}^n{C}_1+\cdots {+}^n{C}_{\lfloor \frac{n}{2}\rfloor }=2^{n-1}$. Now suppose that n is even. Consider the set $$\begin{array}{c}{\mathcal{C}}_1=\widehat{A_0}\cup \left(\underset{\stackrel{i_1\in \left[n\right]}{}}{\cup }\widehat{A_{i_1}}\right)\cup \left(\underset{\stackrel{i_1,i_2\in \left[n\right]}{}}{\cup }\widehat{A_{i_1{i}_2}}\right)\\ \hspace{1em}\cup \cdots \cup \left(\underset{\stackrel{i_r\in \left[n\right]}{1\le r\le \frac{n}{2}¯1}}{\cup }\widehat{A_{i_1{i}_2\cdots i_{\frac{n}{2}¯1}}}\right).\end{array}$$

Note that ${\mathcal{C}}_1$ forms a clique of ${\Gamma }_U(R)$, whereas the set ${\mathcal{C}}_2=\{(a_1,a_2,\dots ,a_n): \text{only} a_{i_1},a_{i_2},\dots ,a_{i_{\frac{n}{2}}}\text{are nonzero}\}$ does not form a clique of ${\Gamma }_U(R)$. Now choose the set $$\begin{array}{c}{\mathcal{C}}_3=\{(b_1,b_2,\dots ,b_n)\in {\mathcal{C}}_2: \text{only} b_{j_1},b_{j_2},\dots ,b_{j_{\frac{n}{2}}}\\ \hspace{1em}\text{are nonzero , where} j_1,j_2,\dots ,j_{\frac{n}{2}}\in \left[n\right]\setminus \{i_1,i_2,\dots ,i_{\frac{n}{2}}\}\}.\end{array}$$

Notice that the set ${\mathcal{C}}_3$ forms a clique in ${\Gamma }_U(R)$. Also, observe that the set ${\mathcal{C}}_1\cup {\mathcal{C}}_3$ forms a clique of the graph ${\Gamma }_U(R)$. Consequently, $\omega ({\mathcal{R}}_{{\Gamma }_U(R)})\ge 2^{n-1}$. To complete the proof, we show that $\chi ({\mathcal{R}}_{{\Gamma }_U(R)})\le 2^{n-1}$. Let $x\in \widehat{A_{i_1{i}_2\cdots i_k}}$ and $y\in \widehat{A_{j_1{j}_2\cdots j_{n¯k}}}$, where $i_1,i_2,\dots ,i_k\in [n]\setminus \{j_1,j_2,\dots ,j_{n-k}\}$. Then note that $x\nsim y$ in ${\Gamma }_U(R)$. Consequently, we can color such vertices with the same color. Therefore, we can color all the vertices of ${\mathcal{R}}_{{\Gamma }_U(R)}$ with $2^{n-1}$ colors. Thus, $\chi ({\mathcal{R}}_{{\Gamma }_U(R)})\le 2^{n-1}$ and so $\omega ({\mathcal{R}}_{{\Gamma }_U(R)})=2^{n-1}$. Hence, by Theorem 2.7, we obtain $$\mathrm{sdim}({\Gamma }_U(R))=|R\setminus U(R)|-2^{n-1}.$$□

Corollary 4.4.

Let $n\ge 2$ be a positive integer and $R\cong {\prod }_{i=1}^n{\mathbb{Z}}_2$. Then $\mathrm{sdim}({\Gamma }_U(R))=2^{n-1}-1$.

Corollary 4.5.

Let $n=p_1^{n_1}{p}_2^{n_2}{p}_3^{n_3}\cdots p_m^{n_m},m\ge 2$. Then the strong metric dimension, $\mathrm{sdim}({\Gamma }_U({\mathbb{Z}}_n))=n-\varphi (n)-2^{m-1}$.

Theorem 4.6.

Let $n\ge 2$ be a positive integer and $R\cong {\prod }_{i=1}^n{\mathbb{Z}}_2$. Then the metric dimension of ${\Gamma }_U(R)$ is given below: $$\beta ({\Gamma }_U(R))=\{\begin{array}{cc}1;\hfill & n=2\hfill \\ n;\hfill & \text{Otherwise}.\hfill \end{array}$$

Proof.

For n = 2, we have ${\Gamma }_U(R)\cong K_1\vee (K_1\cup K_1)$ (see Remark 2.8). Now suppose that $n\ge 3$. Clearly,

$|V({\Gamma }_U(R))|=2^n-1$. By Lemma 2.6, we get $n=f(2^n-1,2)\le \beta ({\Gamma }_U(R))$. To prove the result, we show that there exists a resolving set of size n. Consider the set $\mathcal{R}=\{(0,1,1,\dots ,1),(1,0,1,1,\dots ,1)$, $(1,1,0,1,\dots ,1),\dots ,(1,1,\dots ,1,0)\}$. Let $x=(x_1,x_2,\dots ,x_n),y=(y_1,y_2,\dots ,y_n)\in V({\Gamma }_U(R))$. If one of x and y belongs to $\mathcal{R}$ then there is nothing to prove. We may now suppose that $x,y\notin \mathcal{R}$. Since $x,y\in {\mathbb{Z}}_2\times {\mathbb{Z}}_2\times \cdots \times {\mathbb{Z}}_2$, we have $(x)\ne (y)$. If $x\nsim y$ in ${\Gamma }_U(R)$, then there exists $i\in [n]$ such that x_i = 0 but $y_i\ne 0$. Now choose $z=(z_1,z_2,\dots ,z_n)\in \mathcal{R}$ such that only z_i = 0. Note that $z\sim x$ but $z\nsim y$ in ${\Gamma }_U(R)$. It follows that $d(x,z)\ne d(y,z)$. We may now suppose that $x\sim y$ in ${\Gamma }_U(R)$. Without loss of generality, assume that $(x)\subset (y)$. Then there exists $i\in [n]$ such that x_i = 0 but $y_i\ne 0$. Choose $z=(z_1,z_2,\dots ,z_n)\in \mathcal{R}$ such that only z_i = 0. It follows that $x\sim z$ but $y\nsim z$ in ${\Gamma }_U(R)$. It follows that $d(x,z)\ne d(y,z)$. If $(x)\cancel{\subset }(y)$ and $(y)\cancel{\subset }(x)$, then one can find $z\in \mathcal{R}$ such that $x\in (z)$ but $y\notin (z)$. Consequently, $d(x,z)\ne d(y,z)$. Thus, R is a resolving set. Hence, $\beta ({\Gamma }_U(R))=n$. □

Theorem 4.7.

Let $R\cong F_1\times F_2\times \cdots \times F_n$, where $n\ge 2$ and each $F_i\ne {\mathbb{Z}}_2$. Then $$\beta ({\Gamma }_U(R))=|R\setminus U(R)|-2^n+2.$$

Proof.

Let $R\cong F_1\times F_2\times \cdots \times F_n$, where $n\ge 2$. For each $i_1,i_2,\dots ,i_{n-1}\in [n]$, note that ${\Gamma }_U(R)$ has $2^n-1$ equivalence classes, namely $\widehat{A_0},\widehat{A_{i_1}},\dots ,\widehat{A_{i_1{i}_2\cdots i_{n¯1}}}$ under the relation $\equiv$. Let T be an arbitrary resolving set. Then by Lemma 2.5, T contains at least $\left|\widehat{A_{i_1{i}_2\cdots i_k}}\right|-1$ elements from each equivalence class $\widehat{A_{i_1{i}_2\cdots i_k}}$, where $i_1,i_2,\dots ,i_k\in [n]$ and $1\le k\le n-1$. It follows that $\left|T\right|\ge |R\setminus U(R)|-2^n+2$. Let $\mathcal{R}$ be a set containing exactly $\left|\widehat{A_{i_1{i}_2\cdots i_k}}\right|-1$ elements from $\widehat{A_{i_1{i}_2\cdots i_k}}$, where $i_1,i_2,\dots ,i_k\in [n]$ and $1\le k\le n-1$. Note that $\left|\mathcal{R}\right|=|R\setminus U(R)|-2^n+2$. Now we show that $\mathcal{R}$ is a resolving set. Let $x=(x_1,x_2,\dots ,x_n)$ and $y=(y_1,y_2,\dots ,y_n)$ be arbitrary vertices of ${\Gamma }_U(R)$. If one of x and y belongs to $\mathcal{R}$ then there is nothing to prove. We may now suppose that $x,y\notin \mathcal{R}$. It follows that $(x)\ne (y)$. Then either $x\nsim y$ or $x\sim y$ in ${\Gamma }_U(R)$. If $x\nsim y$ in ${\Gamma }_U(R)$, then there exists $z\in \mathcal{R}$ such that $(z)=(x)$. It follows that $d(x,z)\ne d(y,z)$. Now let $x\sim y$ in ${\Gamma }_U(R)$. Then by the similar argument used in the proof of Theorem 4.6, there exists a $z\in \mathcal{R}$ such that $d(x,z)\ne d(y,z)$. Hence, $\mathcal{R}$ is a resolving set and so $\beta ({\Gamma }_U(R))=|R\setminus U(R)|-2^n+2$. □

Corollary 4.8.

Let $n=p_1^{n_1}{p}_2^{n_2}{p}_3^{n_3}\cdots p_m^{n_m},m\ge 2$. Then the metric dimension, $\beta ({\Gamma }_U({\mathbb{Z}}_n))=n-\varphi (n)-2^m+1$.

5 Perfectness of ${\Gamma }_U(R)$

Let $R\cong R_1\times R_2\times \cdots \times R_n$ be a finite commutative ring with unity, where each R_i is a local ring with maximal ideal ${\mathcal{M}}_i$. In the section, we have investigated the perfectness of ${\Gamma }_U(R)$. We write $x_i=(a_{i1},a_{i2},\dots ,a_{in})\in R$, where $a_{ij}\in R_j$ ($1\le j\le n$). We begin with the following lemma.

Lemma 5.1.

Let R be a non-local commutative ring such that $R\cong R_1\times R_2\times \cdots \times R_n$, where $n\ge 5$. Then ${\Gamma }_U(R)$ is not a perfect graph.

Proof.

Let $n\ge 5$. Consider the set $X=\{(1,0,1,1,0,1,1,\dots ,1),(1,0,0,1,1,\dots ,1),(1,1,0,0,1,1,\dots ,1),(0,1,1,0,1,1,\dots ,1),(0,1,1,1,0,1,1,\dots ,$ $1)\}$. Note that ${\Gamma }_U(X)\cong C_5$. Hence, by Theorem 2.4, ${\Gamma }_U(R)$ is not a perfect graph. □

Lemma 5.2.

Let $(R_i,{\mathcal{M}}_i)$ be a local commutative ring and let $R\cong R_1\times R_2\times \cdots \times R_n$, where $n\ge 3$. If ${\Gamma }_U(R)$ is a perfect graph, then $n\in \{3,4\}$ and each ${\mathcal{M}}_i$ is a principal ideal of R_i.

Proof.

Suppose that the graph ${\Gamma }_U(R)$ is perfect. Then by Lemma 5.1, we have $n\in \{3,4\}$. Let n = 3, that is $R\cong R_1\times R_2\times R_3$. Suppose that one of ${\mathcal{M}}_i$ is not a principal ideal of R_i. Without loss of generality, assume that the maximal ideal ${\mathcal{M}}_1$ of R₁ is not principal. Then R₁ has at least two principal maximal ideals $(a_1)$ and $(a_2)$. Then notice that $\overline{{\Gamma }_U(R)}$ contains an induced cycle $C:(a_1,0,1)\sim (a_2,1,0)\sim (1,0,1)\sim (0,1,1)\sim (1,1,0)\sim (a_1,0,1)$ of length five, which is a contradiction (see Theorem 2.4). Further, let n = 4, that is, $R\cong R_1\times R_2\times R_3\times R_4$. Let if possible, ${\mathcal{M}}_i$ is not a principal maximal ideal for some i. Without loss of generality, assume that ${\mathcal{M}}_1$ is not principal. Then there exist at least two principal maximal ideals, viz. $(a_1)$ and $(a_2)$, of R₁. The subgraph induced by the set $X=\{(a_1,0,1,1),(a_2,0,1,1),(a_2,1,0,1),(1,1,0,0),(a_1,1,1,0)\}$ is isomorphic to C₅ in ${\Gamma }_U(R)$; again a contradiction. Therefore, each ${\mathcal{M}}_i$ is principal. Thus the result holds. □

Lemma 5.3.

Let $(R_i,{\mathcal{M}}_i)$ be a local ring and let $R\cong R_1\times R_2\times \cdots \times R_n$ such that each ${\mathcal{M}}_i$ is principal. Let $x_i=(a_{i1},a_{i2},\dots ,a_{in})$ and $y_l=(b_{l1},b_{l2},\dots ,b_{ln})$. Then $x_i\nsim y_l$ in ${\Gamma }_U(R)$ if and only if both $a_{ij},b_{lj}\notin Z(R_j)$, for each j, $1\le j\le n$.

Proof.

If both $a_{ij},b_{lj}\in Z(R_j)$, then the ideals $(a_{ij})$ and $(b_{lj})$ is contained in ${\mathcal{M}}_j=(m_j)$. Note that the ideals $(x_i)$ and $(y_l)$ is contained in the principal ideal generated by $(1,1,\dots ,1,m_j,1,,1,\dots ,1)$. Thus, $x_i\sim y_l$; a contradiction.

Conversely, assume that both $a_{ij},b_{lj}\notin Z(R_j)$ for each j. If $a_{ij}\in Z(R_j)$, then $b_{lj}\in R_j\setminus Z(R_j)=U(R_j)$. It follows that there does not exists $z_j\in Z(R_j)$ such that $(a_{ij}),(b_{lj})\subseteq (z_j)$ for each j. Therefore, $x_i\nsim y_l$ in ${\Gamma }_U(R)$. □

Proposition 5.4.

Let $(R_i,{\mathcal{M}}_i)$ be a local ring and $R\cong R_1\times R_2\times \cdots \times R_n$, where $n\le 4$ and each ${\mathcal{M}}_i$ is principal. Then ${\Gamma }_U(R)$ does not contain any induced cycle of odd length greater than three.

Proof.

The result is straightforward for n = 1 (cf. Remark 3.1). We first prove the result for n = 4 that is $R\cong R_1\times R_2\times R_3\times R_4$. Let if possible, ${\Gamma }_U(R)$ contains an induced cycle $C:x_1\sim x_2\sim x_3\sim \cdots \sim x_k\sim x_1$, where $k\ge 5$ is an odd integer. For $2\le i\le k-1$, note that $x_{i-1}\sim x_i\sim x_{i+1}$ but $x_i\nsim x_t$ where $t\notin \{i-1,i+1\}$. Consider $x_i=(a_{i1},a_{i2},a_{i3},a_{i4})\in R$. Since $x_1\nsim x_3$, by Lemma 5.3, both $a_{11},a_{31}\notin Z(R_1)$. Without loss of generality, assume that $a_{11}\in U(R_1)$. Since x₁ is a non-unit element of R, we have $a_{1j}\in Z(R_j)$ for some $j\in \{2,3,4\}$. Without loss of generality, assume that $a_{12}\in Z(R_2)$. By Lemma 5.3, $a_{32}\in U(R_2)$. Since $x_1\nsim x_3$, we get both $a_{13},a_{33}\notin Z(R_3)$. Now we have the following cases:

Case-1: $a_{13}\in U(R_3)$. First suppose that $a_{14}\in U(R_4)$. Since $x_k\sim x_1\sim x_2$, we get $a_{k2},a_{22}\in Z(R_2)$. It follows that $x_2\sim x_k$ in ${\Gamma }_U(R)$, which is not possible. We may now suppose that $a_{14}\in Z(R_4)$. By Lemma 5.3, we obtain $a_{34},a_{44}\in U(R_4)$. Since x₃ is a non-unit element of R we have either $a_{31}\in Z(R_1)$ or $a_{33}\in Z(R_3)$. Let $a_{31}\in Z(R_1)$. If $a_{33}\in U(R_3)$, then $a_{21},a_{41}\in Z(R_1)$. It follows that $x_2\sim x_4$, which is not possible. Therefore, $a_{33}\in Z(R_3)$. Since $x_3\nsim x_5$, we obtain that $a_{51}\in U(R_1)$ and $a_{53}\in U(R_3)$. Consequently, $x_4\nsim x_5$; a contradiction. Thus, $a_{31}\in U(R_1)$ and so $a_{33}\in Z(R_3)$. Since $x_2\sim x_3\sim x_4$, we must have $a_{23},a_{43}\in Z(R_3)$. It follows that $x_2\sim x_4$. Thus, the case $a_{13}\in U(R_3)$ is not possible.

Case-2: $a_{33}\in U(R_3)$. Since $x_1\nsim x_4$, we have $a_{43}\in U(R_3)$. Since x₃ is a non-unit element of R we have either $a_{31}\in Z(R_1)$ or $a_{34}\in Z(R_4)$. Let $a_{31}\in Z(R_1)$. If $a_{34}\in U(R_4)$, then both $a_{21},a_{41}\in Z(R_1)$ so that $x_2\sim x_4$; a contradiction. Therefore, $a_{34}\in Z(R_4)$. Since $x_3\nsim x_5$, we must have $a_{51}\in U(R_1)$ and $a_{54}\in U(R_4)$. It follows that $x_4\nsim x_5$ in ${\Gamma }_U(R)$; again a contradiction. Therefore, $a_{31}\in U(R_1)$ and $a_{34}\in Z(R_4)$. Consequently, $x_2\sim x_4$; a contradiction. Therefore, the case $a_{33}\in U(R_3)$ is not possible.

Thus, there does not exists an induced cycle of odd length greater than three. The proof is similar when $R\cong R_1\times R_2\times R_3$ or $R\cong R_1\times R_2$. □

Proposition 5.5.

Let $(R_i,{\mathcal{M}}_i)$ be a local ring and $R\cong R_1\times R_2\times \cdots \times R_n$, where $n\le 4$ and each ${\mathcal{M}}_i$ is principal. Then $\overline{{\Gamma }_U(R)}$ does not contain any induced cycle of odd length greater than three.

Proof.

The result is straightforward for n = 1 (cf. Remark 3.1). Now, let $R\cong R_1\times R_2\times R_3\times R_4$. On contrary, suppose that $\overline{{\Gamma }_U(R)}$ contains an induced cycle of odd length greater than three, namely $C:y_1\sim y_2\sim y_3\sim \cdots \sim y_k\sim y_1$ and $k\ge 5$. Let $y_i=(b_{i1},b_{i2},b_{i3},b_{i4})\in R$. Since $y_1\sim y_2$ in $\overline{{\Gamma }_U(R)}$, by Lemma 5.3, both $b_{11},b_{21}\notin Z(R_1)$. Without loss of generality, assume that $b_{11}\in U(R_1)$. Since y₁ is a non-unit element of R, we have $b_{1j}\in Z(R_j)$, for some $j\in \{2,3,4\}$. Without loss of generality, assume that $b_{12}\in Z(R_2)$. By Lemma 5.3, we get $b_{22}\in U(R_2)$. Since $y_1\sim y_2$ in $\overline{{\Gamma }_U(R)}$, we get both $b_{13},b_{23}\notin Z(R_3)$. Now we have the following cases:

Case-1: $b_{13}\in U(R_3)$. Let $b_{14}\in U(R_4)$. Since $y_1\nsim y_3$ and $y_1\nsim y_4$ in $\overline{{\Gamma }_U(R)}$, we get $b_{32},b_{42}\in Z(R_2)$. It follows that $y_3\nsim y_4$, which is not possible. We may now suppose that $b_{14}\in Z(R_4)$. It follows that $b_{24},b_{k4}\in U(R_4)$. Since y₂ is a non-unit element of R, we have either $b_{21}\in Z(R_1)$ or $b_{23}\in Z(R_3)$. Let $b_{21}\in Z(R_1)$. If $b_{23}\in U(R_3)$, then $b_{k1},b_{(k-1)1}\in Z(R_1)$. It follows that $y_k\nsim y_{k-1}$ in $\overline{{\Gamma }_U(R)}$, which is not possible. Therefore, $b_{23}\in Z(R_3)$. Since $y_2\sim y_3$, we obtain that $b_{31}\in U(R_1)$ and $b_{33}\in U(R_3)$. The adjacency of y₁ with y_k follows that $b_{k2}\in U(R_2)$ and $b_{k4}\in U(R_4)$. It follows that $y_3\sim y_k$ in $\overline{{\Gamma }_U(R)}$; a contradiction. Therefore, $b_{21}\notin Z(R_1)$. We may now suppose that $b_{23}\in Z(R_3)$. Since $y_2\nsim y_k$ and $y_2\nsim y_{k-1}$ in $\overline{{\Gamma }_U(R)}$, we have $b_{k3},b_{(k-1)3}\in Z(R_3)$. It follows that $y_k\nsim y_{k-1}$. Thus, the case $b_{13}\in U(R_3)$ is not possible.

Case-2: $b_{23}\in U(R_3)$. First suppose that $b_{24}\in U(R_4)$. Since y₂ is a non-unit element of R, we have $b_{21}\in Z(R_1)$. Note that $y_2\nsim y_k$ and $y_2\nsim y_{k-1}$ in $\overline{{\Gamma }_U(R)}$ so that $b_{k1},b_{(k-1)1}\in Z(R_1)$. It follows that $y_k\nsim y_{k-1}$; a contradiction. Therefore, $b_{24}\in Z(R_4)$. Since $y_1\sim y_2\sim y_3$ in $\overline{{\Gamma }_U(R)}$, we have $b_{14},b_{34}\in U(R_4)$. First suppose that $b_{21}\in U(R_1)$. Since $y_2\nsim y_k$ and $y_2\nsim y_{k-1}$ in $\overline{{\Gamma }_U(R)}$, we have $b_{k4},b_{(k-1)4}\in Z(R_4)$. It follows that $y_k\nsim y_{k-1}$; a contradiction. We may now suppose that $b_{21}\in Z(R_1)$. It follows that $b_{31}\in U(R_1)$. Since y₃ is a non-unit element of R, we have either $b_{32}\in Z(R_2)$ or $b_{33}\in Z(R_3)$.

Let $b_{32}\in Z(R_2)$. The adjacency of y₃ with y₄ implies that $b_{42}\in U(R_2)$. If $b_{33}\in U(R_3)$, then $b_{k2},b_{12}\in Z(R_2)$. It follows that $y_1\nsim y_k$ in $\overline{{\Gamma }_U(R)}$, which is not possible. Therefore, $b_{33}\in Z(R_3)$. Since $y_3\sim y_4$, we have $b_{42}\in U(R_2)$ and $b_{43}\in U(R_3)$. Since y₄ is a non-unit element of R, we have either $b_{41}\in Z(R_1)$ or $b_{44}\in Z(R_4)$. If $b_{41}\in Z(R_1)$ and $b_{44}\in U(R_4)$, then $y_1\sim y_4$; a contradiction. Therefore, $b_{44}\in Z(R_4)$. The adjacency of y₄ with y₅ follows that $b_{51}\in U(R_1)$ and $b_{54}\in U(R_4)$. It follows that $y_2\sim y_5$ in $\overline{{\Gamma }_U(R)}$; a contradiction. Thus, $b_{41}\in U(R_1)$. Consequently, $b_{44}\in Z(R_4)$. Since $y_2\nsim y_4$ and $y_1\nsim y_4$, we have $b_{14},b_{24}\in Z(R_4)$. It follows that $y_1\nsim y_2$ in $\overline{{\Gamma }_U(R)}$; a contradiction. Therefore, this case is not possible.

Thus, $\overline{{\Gamma }_U(R)}$ does not contain an induced cycle of odd length greater than three. The proof is similar when $R\cong R_1\times R_2\times R_3$ or $R\cong R_1\times R_2$. □

By combining Lemma 5.2, and Propositions 5.4, 5.5, we get the following theorem.

Theorem 5.6.

Let $(R_i,{\mathcal{M}}_i)$ be a local ring and $R\cong R_1\times R_2\times \cdots \times R_n$, where $n\ge 3$. Then ${\Gamma }_U(R)$ is a perfect graph if and only if $n\in \{3,4\}$ and each ideal ${\mathcal{M}}_i$ of R_i is principal.

In view of Propositions 5.4 and 5.5, we have the following lemma.

Lemma 5.7.

Let $(R_i,{\mathcal{M}}_i)$ be a local ring and $R\cong R_1\times R_2\times \cdots \times R_n$, where $n\in \{1,2\}$ and each ${\mathcal{M}}_i$ is principal. Then ${\Gamma }_U(R)$ is a perfect graph.

Corollary 5.8.

The graph ${\Gamma }_U({\mathbb{Z}}_n)$ is perfect if and only if $n=p_1^{n_1}{p}_2^{n_2}{p}_3^{n_3}{p}_4^{n_4}$, where p_i’s are distinct prime numbers and $n_i\in \mathbb{N}\cup \left\{0\right\}$.

Proposition 5.9.

Let $R\cong R_1\times R_2$ such that R₁, R₂ are local rings with maximal ideals ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$, respectively. If both ${\mathcal{M}}_1,{\mathcal{M}}_2$ are not principal, then ${\Gamma }_U(R)$ is not a perfect graph.

Proof.

Let $R\cong R_1\times R_2$ and each ${\mathcal{M}}_1,{\mathcal{M}}_2$ are not principal ideal of R₁, R₂, respectively. Then R₁ and R₂ has at least two principal maximal ideal, namely, $(a_1),(a_2)$ and $(b_1),(b_2)$, respectively. Observe that the set $X=\{(a_1,b_1),(a_2,b_2),(1,b_1),(a_1,b_2),(a_2,b_1)\}$ induces C₅ in $\overline{{\Gamma }_U(R)}$. Therefore, ${\Gamma }_U(R)$ is not a perfect graph. □

Based on our computation for various local rings of small order given in [31] and reference therein, we propose the following conjecture.

Conjecture: Let $R\cong R_1\times R_2$ such that $R_1,R_2$ are local rings with maximal ideals ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$, respectively. Then ${\Gamma }_U(R)$ is a perfect graph if and only if either ${\mathcal{M}}_1$ or ${\mathcal{M}}_2$ is principal.

6 Upper ideal relation graph of the ring ${\mathbb{Z}}_n$

In this section, we study the upper ideal relation graph of the ring ${\mathbb{Z}}_n$. We obtain the vertex connectivity and the automorphism group of ${\Gamma }_U({\mathbb{Z}}_n)$. Moreover, we classify all the value of n such that ${\Gamma }_U({\mathbb{Z}}_n)$ is Hamiltonian. Finally, we obtain the spectrum of ${\Gamma }_U({\mathbb{Z}}_n)$ for $n=p^{\alpha }{q}^{\beta }$, where $\alpha ,\beta$ are non-negative integers and p, q are prime numbers. First, we discuss about the structure of the graph ${\Gamma }_U({\mathbb{Z}}_n)$. An integer d such that $1<d<n$ is called a proper divisor of n if $d|n$. The greatest common divisor of two elements a, b is denoted by (a, b). Let $d_1,d_2,\dots ,d_k$ be the distinct proper divisors of n. For $1\le i\le k$, consider the following sets $${\mathcal{A}}_{d_i}=\{x\in {\mathbb{Z}}_n:(x,n)=d_i\}\text{and}{\mathcal{A}}_n=\left\{0\right\}$$

Note that for $x,y\in {\mathcal{A}}_{d_i}$, we have $(x)=(y)=(d_i)$. Moreover, the sets ${\mathcal{A}}_{d_1},{\mathcal{A}}_{d_2},\dots ,{\mathcal{A}}_{d_k}$ and ${\mathcal{A}}_n$ forms a partition of $V({\Gamma }_U({\mathbb{Z}}_n))$. The following lemma is useful in the sequel.

Lemma 6.1.

[46] $\left|{\mathcal{A}}_{d_i}\right|=\varphi \left(\frac{n}{d_i}\right)$ for $1\le i\le k$, where $\varphi$ is Euler’s totient function.

Lemma 6.2.

Let $x\in {\mathcal{A}}_{d_i}$ and $y\in {\mathcal{A}}_{d_j}$, where $1\le i,j\le k$. Then $x\sim y$ in ${\Gamma }_U({\mathbb{Z}}_n)$ if and only if there exists a proper divisor d of n such that $d|x$ and $d|y$.

Proof.

First suppose that $x\sim y$. Then $x,y\in (z)$ for some $z\in V({\Gamma }_U({\mathbb{Z}}_n))$. It follows that $z\in {\mathcal{A}}_d$ for some proper divisor d of n. Therefore, $x,y\in (d)$. Consequently, $d|x$ and $d|y$. Conversely, assume that $d|x$ and $d|y$. It implies that $x,y\in (d)$. Consequently, $x\sim y$. □

Corollary 6.3.

For every $x,y\in {\mathcal{A}}_{d_i}$, we have $x\sim y$ in ${\Gamma }_U({\mathbb{Z}}_n)$.

Theorem 6.4.

For distinct primes p and q, the graph ${\Gamma }_U({\mathbb{Z}}_n)$ is Hamiltonian if and only if $n\ne 4$ and $n\ne pq$.

Proof.

First suppose that the graph ${\Gamma }_U({\mathbb{Z}}_n)$ is Hamiltonian. Let n = pq. Note that ${\mathbb{Z}}_{pq}\cong K_1\vee (K_{q-1}\cup K_{p-1})$, which is not a Hamiltonian graph. For $n=4$, we have ${\Gamma }_U({\mathbb{Z}}_4)\cong K_2$ and therefore ${\Gamma }_U({\mathbb{Z}}_4)$ is not a Hamiltonian graph. Conversely, assume that $n\ne 4$ and $n\ne pq$. If n = p then $V({\Gamma }_U({\mathbb{Z}}_n))=\left\{0\right\}$, which is trivially a Hamiltonian graph. If $n=p^r$, where $r\ge 2$, then ${\Gamma }_U({\mathbb{Z}}_{p^r})\cong K_{p^{r-1}}$. Since $n\ne 4$, we have ${\Gamma }_U({\mathbb{Z}}_{p^r})$ is a complete graph of at least three vertices. Thus ${\Gamma }_U({\mathbb{Z}}_{p^r})$ is Hamiltonian. We may now suppose that $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}{p}_3^{{\alpha }_3}\cdots p_m^{{\alpha }_m}$, where $m\ge 2$. Note that $(p_1),(p_2),\dots ,(p_m)$ are m distinct maximal ideals of ${\mathbb{Z}}_n$ and the subgraph of ${\Gamma }_U({\mathbb{Z}}_n)$ induced by each of these ideals forms a clique in ${\Gamma }_U({\mathbb{Z}}_n)$. Further, note that for any two distinct maximal ideals $(p_i)$ and $(p_j)$, we have $(p_i)\sim p_i{p}_j\sim (p_j)$. One can construct a Hamiltonian cycle using the adjacency $0\sim (p_1)\sim p_1{p}_2\sim (p_2)\sim \cdots \sim p_{m-1}{p}_m\sim (p_m)$. Hence, the graph ${\Gamma }_U({\mathbb{Z}}_n)$ is Hamiltonian. □

Now we obtain the vertex connectivity of ${\Gamma }_U({\mathbb{Z}}_n)$. By Remark 3.1, we have $\kappa ({\Gamma }_U({\mathbb{Z}}_{p^{\alpha }}))=p^{\alpha -1}-1$. If $n=p^{\alpha }{q}^{\beta }$, then note that ${\Gamma }_U({\mathbb{Z}}_n)\cong K_{|(pq)|}\vee (K_{|(p)\setminus (pq)|}\cup K_{|(q)\setminus (pq)|})$. It follows that $\kappa ({\Gamma }_U({\mathbb{Z}}_n))=|(pq)|=p^{\alpha -1}{q}^{\beta -1}$. For distinct primes divisors $p_1,p_2,\dots ,p_r$ of n, we define the set $$\begin{array}{c}{(p_1{p}_2\cdots p_r)}^{♭}=\{u{p}_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_r^{{\alpha }_r}:u\in U({\mathbb{Z}}_n)\text{and}{\alpha }_i\\ >0\text{for each}i\in \{1,2,\dots ,r\}\}\end{array}$$

Lemma 6.5.

Let $n=p_1^{n_1}{p}_2^{n_2}\cdots p_{r-1}^{n_{r-1}}{p}_r^{n_r}{p}_{r+1}^{n_{r+1}}\cdots p_m^{n_m}$, where p_i’s are distinct primes and $r\le m-2$. If p_k < p_t with $k,t\notin \{1,2,\dots ,r\}$, then $\left|{(p_1{p}_2\cdots p_r{p}_t)}^{♭}\right|\le \left|{(p_1{p}_2\cdots p_r{p}_k)}^{♭}\right|.$

Proof.

Let $x=u{p}_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_r^{{\alpha }_r}{p}_t^{{\alpha }_t}$ and $y=u{p}_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_r^{{\alpha }_r}{p}_k^{{\alpha }_t}$ such that x < n. Then note that the map $\psi :{(p_1{p}_2\cdots p_r{p}_t)}^{♭}\to {(p_1{p}_2\cdots p_r{p}_k)}^{♭}$ defined by $\psi (x)=y$ is a one-one map. Thus, the result holds. □

Theorem 6.6.

For $m\ge 3$, let $n=p_1^{n_1}{p}_2^{n_2}\cdots p_m^{n_m}$, where p_i’s are distinct primes and $p_1<p_2<\cdots <p_m$. Then the set $$T=(p_1{p}_m)\cup (p_2{p}_m)\cup \cdots \cup (p_{m-1}{p}_m)$$is a cut set of ${\Gamma }_U({\mathbb{Z}}_n)$. Moreover, the vertex connectivity of ${\Gamma }_U({\mathbb{Z}}_n)$ is $\left|T\right|$.

Proof.

To prove, T is a cut set of ${\Gamma }_U({\mathbb{Z}}_n)$, we show that the subgraph induced by $V({\Gamma }_U({\mathbb{Z}}_n))\setminus T$ is disconnected. Let $x\in (p_m)\setminus T$ and $y\in (p_r)\setminus T$, where $r\ne m$. Assume that $x\sim y$. Then there exists a proper divisor d of n such that $d|x$ and $d|y$. Consequently, $d\in (p_r{p}_m)\subseteq T$. It follows that $x,y\in T$; a contradiction. Thus, $x\in (p_m)\setminus T$ is not adjacent to any $y\in (p_r)\setminus T$, where $r\ne m$. Therefore, there is no path between x and y in ${\Gamma }_U({\mathbb{Z}}_n)$. Hence, T is a cut set. To obtain the vertex connectivity of ${\Gamma }_U({\mathbb{Z}}_n)$, we show that T is a minimum cut set. In this connection, we show that there are at least $\left|T\right|$ vertex disjoint paths between x and y in ${\Gamma }_U({\mathbb{Z}}_n)$ (see [44, Theorem 4.2.21]). We discuss the following cases.

Case-1: $x,y\in (p_i)$. Since the subgraph induced by $(p_i)$ forms a complete subgraph; we get $|(p_i)|-1$ vertex disjoint paths between x and y. Note that $T\subset (p_m)$ and for each p_i, we have $|(p_i)|\ge |(p_m)|$. Consequently, there exist at least $\left|T\right|$ vertex disjoint paths between x and y.

Case-2: $x\in (p_i),y\in (p_j)$ such that p_i > p_j and $i\ne m$. Then for any prime divisor $p_r(r\ne i,j,m)$ of n, we get the paths $x\sim u\sim v\sim w\sim y$, where $u\in {(p_i{p}_r)}^{♭},v\in {(p_r{p}_m)}^{♭},w\in {(p_r{p}_j)}^{♭}$. By Lemma 6.5, $\left|{(p_i{p}_r)}^{♭}\right|,\left|{(p_r{p}_j)}^{♭}\right|>\left|{(p_r{p}_m)}^{♭}\right|$, we obtain at least $\left|{(p_r{p}_m)}^{♭}\right|$ vertex disjoint paths between x and y. Analogously, for $z\in {(p_i{p}_m)}^{♭},z\prime \in {(p_j{p}_m)}^{♭}$, we get the paths $x\sim z\sim z\prime \sim y$ between x and y in ${\Gamma }_U({\mathbb{Z}}_n)$. Note that we have $\left|{(p_i{p}_m)}^{♭}\right|$ vertex disjoint paths between x and y. In addition to these paths, we also have $x\sim z\sim y$, where $z\in {(p_i{p}_j)}^{♭}$. It follows that we have at least $\left|{(p_j{p}_m)}^{♭}\right|$ vertex disjoint paths because $\left|{(p_i{p}_j)}^{♭}\right|>\left|{(p_j{p}_m)}^{♭}\right|$. Consequently, we get at least ${\sum }_{i_1=1}^{m-1}\left|{(p_{i_1}{p}_m)}^{♭}\right|$ vertex disjoint paths between x and y in ${\Gamma }_U({\mathbb{Z}}_n)$. Similarly, we have following additional vertex disjoint paths between x and y $$\begin{array}{c}x\sim u\sim v\sim w\sim y,\text{where }u\in {(p_i{p}_r{p}_{r\prime })}^{♭},v\in {(p_r{p}_{r\prime }{p}_m)}^{♭},\\ \mathrm{\hspace{1em}}\mathrm{\hspace{1em}}u\in {(p_r{p}_{r\prime }{p}_j)}^{♭}\\ x\sim z\sim z\prime \sim y,\text{where }z\in {(p_i{p}_r{p}_m)}^{♭},z\prime \in {(p_j{p}_r{p}_m)}^{♭}\\ x\sim z″\sim y,\text{where }z″\in {(p_i{p}_r{p}_j)}^{♭}\\ x\sim z″\prime \sim y,\text{where }z″\prime \in {(p_i{p}_j{p}_m)}^{♭}.\end{array}$$

Consequently, we get at least ${\sum }_{i_1<i_2}^{}\left|{(p_{i_1}{p}_{i_2}{p}_m)}^{♭}\right|$ vertex disjoint paths between x and y. On continuing in this way, we shall get at least $$\begin{array}{c}l=\sum _{i_1=1}^{m-1}\left|{(p_{i_1}{p}_m)}^{♭}\right|+\sum _{i_1<i_2}^{}\left|{(p_{i_1}{p}_{i_2}{p}_m)}^{♭}\right|+\cdots +\\ \times \sum _{i_1<i_2<\cdots <i_{m-2}}^{}\left|{(p_{i_1}{p}_{i_2}\cdots p_{i_{m-2}}{p}_m)}^{♭}\right|+\left|{(p_{i_1}{p}_{i_2}\cdots p_{m-1}{p}_m)}^{♭}\right|\end{array}$$vertex disjoint paths between x and y. Also note that $\left|T\right|=l$. Thus, we have at least $\left|T\right|$ vertex disjoint paths between x and y in ${\Gamma }_U({\mathbb{Z}}_n)$.

Case-3: $x\in (p_i),y\in (p_m)$ and $i\ne m$. Then, for any prime divisor $p_r(r\ne i,m)$ of n, we get the following vertex disjoint paths $$\begin{array}{c}x\sim u\sim v\sim y,\text{where }u\in {(p_i{p}_r)}^{♭},v\in {(p_r{p}_m)}^{♭}\\ x\sim z\sim y,\text{where }z\in {(p_i{p}_m)}^{♭}.\end{array}$$

Consequently, we get at least ${\sum }_{i_1=1}^{m-1}\left|{(p_{i_1}{p}_m)}^{♭}\right|$ vertex disjoint path between x and y. Now in the similar lines of the Case-2, we shall get at least $l=\left|T\right|$ vertex disjoint paths between x and y. Thus, the result follows. □

6.1 Automorphism group of ${\Gamma }_U({\mathbb{Z}}_n)$

An automorphism of a graph Γ is a permutation f on $V(\Gamma )$ with the property that, for any vertices u and v, we have $f(u)\sim f(v)$ if and only if $u\sim v$. The set $\text{Aut}(\Gamma )$ of all graph automorphisms of a graph Γ forms a group with respect to composition of mappings. In this subsection, we obtain the automorphism group $\text{Aut}({\Gamma }_U({\mathbb{Z}}_n))$ of the ring ${\mathbb{Z}}_n$. For $n=p_1^{n_1}{p}_2^{n_2}{p}_3^{n_3}\cdots p_m^{n_m}$, consider the following sets $$\begin{array}{c}{X}_{p_1}=\underset{i=1}{\overset{n_1}{\cup }}{\mathcal{A}}_{p_1^i},X_{p_2}=\underset{i=1}{\overset{n_2}{\cup }}{\mathcal{A}}_{p_2^i},\dots ,X_{p_m}=\underset{i=1}{\overset{n_m}{\cup }}{\mathcal{A}}_{p_m^i},\\ X_{p_1{p}_2}=\underset{i=1}{\overset{n_1}{\cup }}\left(\underset{j=1}{\overset{n_2}{\cup }}{\mathcal{A}}_{p_1^i{p}_2^j}\right),\dots ,X_{p_{\alpha }{p}_{\beta }}=\underset{i=1}{\overset{n_{\alpha }}{\cup }}\left(\underset{j=1}{\overset{n_{\beta }}{\cup }}{\mathcal{A}}_{p_{\alpha }^i{p}_{\beta }^j}\right),\\ ⋮\\ X_{p_{i_1}{p}_{i_2}\cdots p_{i_k}}=\underset{j_1=1}{\overset{n_{i_1}}{\cup }}\underset{j_2=1}{\overset{n_{i_2}}{\cup }}\cdots \underset{j_k=1}{\overset{n_{i_k}}{\cup }}{\mathcal{A}}_{p_{i_1}^{j_1}{p}_{i_2}^{j_2}\cdots p_{i_k}^{j_k}},k<m\\ ⋮\\ X_{p_1{p}_2\cdots p_m}=\underset{i_1=1}{\overset{n_1}{\cup }}\underset{i_2=1}{\overset{n_2}{\cup }}\cdots \underset{i_m=1}{\overset{n_m}{\cup }}{\mathcal{A}}_{p_1^{i_1}{p}_2^{i_2}\cdots p_m^{i_m}}.\end{array}$$

Lemma 6.7.

Let $x\in X_r$. Then $x\in (r)$.

Proof.

Without loss of generality, let $r=p_1{p}_2\cdots p_k$. Then $x\in {\mathcal{A}}_{p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}}$, where $1\le {\alpha }_i\le n_i$. It follows that $(x)=(p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k})$. Thus, the result holds. □

Lemma 6.8.

Let $x,y\in V({\Gamma }_U({\mathbb{Z}}_n))$. Then $x,y\in X_r$ if and only if $N[x]=N[y]$.

Proof.

Let $x,y\in X_r$. Then by Lemma 6.2 and Corollary 6.3, $x\sim y$. Now suppose $z\sim x$ for some $z\in V({\Gamma }_U({\mathbb{Z}}_n))$. By Lemma 6.2, there exists a prime divisor p of n such that $p|x$ and $p|z$. It follows that $x,z\in (p)$. Since $x\in X_r$, by Lemma 6.7, we have $p|r$. Consequently, we get $y\in (p)$. It implies that $y\sim z$. Conversely, let $N[x]=N[y]$. For any prime divisor p of n, note that if $p|x$ then $p|y$ and vice-versa. Now suppose $x\in X_r$ and $y\in X_{r\prime }$ with $r\ne r\prime$. Then, without loss of generality, there exists a prime divisor q of n such that $q|r$ but $q\nmid r\prime$; a contradiction. □

Corollary 6.9.

Let $x,y\in X_r$. Then $\mathrm{deg}(x)=\text{ deg}(y)$.

Theorem 6.10.

Let $n=p_1^{n_1}{p}_2^{n_2}{p}_3^{n_3}\cdots p_m^{n_m}$. Then $\text{Aut}({\Gamma }_U({\mathbb{Z}}_n))\cong S_{\left|X_{p_1}\right|}\times S_{\left|X_{p_2}\right|}\times \cdots \times S_{\left|X_{p_1{p}_2\cdots p_m}\right|}$, where $S_{\left|X\right|}$ denotes the symmetric group of degree $\left|X\right|$.

Proof.

By Lemma 6.8, the vertices of each partition set X_r have same adjacency with the other vertices of ${\Gamma }_U({\mathbb{Z}}_n)$. Thus, for each r, the vertices of X_r can be permuted among themselves.

Now we show that a vertex of X_r cannot be map to a vertex of $X_{r\prime }$ $(r\ne r\prime )$ under an automorphism f of ${\Gamma }_U({\mathbb{Z}}_n)$. Let $x\in X_r$ and $y\in X_{r\prime }$ with $r\ne r\prime$. Suppose f(x) = y. Let $p_{i_1},p_{i_2},\dots ,p_{i_k}$ be the prime divisors of n which divides either x or y but not both. Let $p_i=\max \{p_{i_1},p_{i_2},\dots ,p_{i_k}\}$. Without loss of generality assume that p_i divides x but not y. Thus, we have $x\sim p_i$. We know that $\mathrm{deg}(p_i)=\frac{n}{p_i}-1$. Let $f(p_i)=t$. Since f is an automorphism, we get $t\sim y$ and $\mathrm{deg}(t)=\frac{n}{p_i}-1$. It implies that $t\in (p_i)$. Consequently, we get $y\in (p_i)$ and $p_i|y$; a contradiction. Hence, the result holds. □

6.2 Spectrum of ${\Gamma }_U({\mathbb{Z}}_n)$

In this subsection, we obtain the Laplacian and normalized Laplacian spectrum of the ring ${\mathbb{Z}}_n$, for $n=p^{\alpha }{q}^{\beta }$, where α, β are non-negative integers and p, q are distinct primes. For a finite simple (without multiple edge and loops) undirected graph Γ with vertex set $V(\Gamma )=\{u_1,u_2,\dots ,u_k\}$, the adjacency matrix $A(\Gamma )$ is defined as the k × k matrix whose $(i,j)th$ entry is 1 if $u_i\sim u_j$ and 0 otherwise. We denote the diagonal matrix by $D(\Gamma )=\text{diag}(d_1,d_2,\dots ,d_k)$, where d_i is the degree of the vertex u_i of Γ. The Laplacian matrix $\mathcal{L}(\Gamma )$ of Γ is the matrix $D(\Gamma )-A(\Gamma )$. The eigenvalues of $\mathcal{L}(\Gamma )$ are called the Laplacian eigenvalues of Γ. Now let ${\lambda }_1(\Gamma ),{\lambda }_2(\Gamma ),\dots ,{\lambda }_r(\Gamma )$ be the distinct eigenvalues of $\mathcal{L}(\Gamma )$ with multiplicities ${\mu }_1,{\mu }_2,\dots ,{\mu }_r$, respectively. The Laplacian spectrum of Γ, that is the spectrum of $\mathcal{L}(\Gamma )$, is represented as $$\Phi (\mathcal{L}(\Gamma ))=\left(\begin{array}{cccc}{\lambda }_1(\Gamma )& {\lambda }_2(\Gamma )& \cdots & {\lambda }_r(\Gamma )\\ {\mu }_1& {\mu }_2& \cdots & {\mu }_r\end{array}\right).$$

The normalized Laplacian introduced by Chung [17] and it is defined as $L(\Gamma )=D{(\Gamma )}^{\frac{-1}{2}}\mathcal{L}(\Gamma )D{(\Gamma )}^{\frac{-1}{2}}$. The following results are useful in the sequel.

Theorem 6.11.

[29] Let ${\Gamma }_1\vee {\Gamma }_2$ denotes the join of two graphs ${\Gamma }_1$ and ${\Gamma }_2$. Then the characteristic polynomial of the $\mathcal{L}({\Gamma }_1\vee {\Gamma }_2)$ is $$\mu ({\Gamma }_1\vee {\Gamma }_2,x)=\frac{x(x-n_1-n_2)}{(x-n_1)(x-n_2)}\mu ({\Gamma }_1,x-n_2)\mu ({\Gamma }_2,x-n_1).$$where n₁, n₂ are the orders of graph ${\Gamma }_1$ and ${\Gamma }_2$, respectively.

Theorem 6.12.

[29] Let Γ be the disjoint union of graphs ${\Gamma }_1,{\Gamma }_2,\dots ,{\Gamma }_k$. Then the characteristic polynomial of the $\mathcal{L}(\Gamma )$ is $$\mu (\Gamma ,x)=\prod _{i=1}^k\mu ({\Gamma }_i,x).$$

The proof of the following lemma is straightforward.

Lemma 6.13.

The adjacency spectrum of the complete graph on n vertices is $\left(\begin{array}{cc}n-1& -1\\ 1& n-1\end{array}\right)$.

Lemma 6.14.

[37] Let Γ be a graph of order n and let Γ_i be the r_i regular graph on n_i vertices, having adjacency eigenvalues ${\lambda }_{i1}=r_i\ge {\lambda }_{i2}\ge \cdots \ge {\lambda }_{i{n}_i}$, where $i=1,2,\dots ,n$. Then the normalized Laplacian eigenvalues of the graph $\Gamma [{\Gamma }_1,{\Gamma }_2,\dots ,{\Gamma }_n]$ consists of the eigenvalues $1-\frac{1}{r_i+{\alpha }_i}{\lambda }_{ik}({\Gamma }_i)$, for $i=1,2,\dots ,n$ and $k=2,3,\dots ,n_i$, where ${\alpha }_i={\sum }_{v_j\in N_{\Gamma }(v_i)}^{}{n}_i$ is the sum of the orders of the graphs ${\Gamma }_j,j\ne i$, which correspond to the neighbors of the vertex $v_i\in \Gamma$. The remaining n eigenvalues are the eigenvalues of the matrix $$\left[\begin{array}{cccc}\frac{{\alpha }_1}{{\alpha }_1+r_1}& \frac{-n_2{a}_{12}}{\sqrt{(r_1+{\alpha }_1)(r_2+{\alpha }_2)}}& \cdots & \frac{-n_n{a}_{1n}}{\sqrt{(r_1+{\alpha }_1)(r_n+{\alpha }_n)}}\\ \frac{-n_1{a}_{21}}{\sqrt{(r_2+{\alpha }_2)(r_1+{\alpha }_1)}}& \frac{{\alpha }_2}{{\alpha }_2+r_2}& \cdots & \frac{-n_n{a}_{2n}}{\sqrt{(r_2+{\alpha }_2)(r_n+{\alpha }_n)}}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{-n_1{a}_{n1}}{\sqrt{(r_n+{\alpha }_n)(r_1+{\alpha }_1)}}& \frac{-n_2{a}_{n2}}{\sqrt{(r_n+{\alpha }_n)(r_2+{\alpha }_2)}}& \cdots & \frac{{\alpha }_n}{{\alpha }_n+r_n}\end{array}\right]$$where, $$a_{ij}=\{\begin{array}{cc}1,\hfill & v_i\sim v_j\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$

6.2.1 Laplacian spectrum of ${\Gamma }_U({\mathbb{Z}}_n)$

In this subsection, we find the Laplacian spectra of ${\Gamma }_U({\mathbb{Z}}_n)$ for $n=p^{\alpha }{q}^{\beta }$, where p, q are distinct primes. By Remark 3.1, the Laplacian eigenvalues of ${\Gamma }_U({\mathbb{Z}}_{p^{\alpha }})$ are 0 and $p^{\alpha -1}$ with multiplicity 1 and $p^{\alpha -1}-1$, respectively.

Theorem 6.15.

Let $n=p^{\alpha }{q}^{\beta }$. Then the Laplacian spectrum of ${\Gamma }_U({\mathbb{Z}}_n)$ is given by $$\left(\begin{array}{ccccc}0& t& t(p+q-1)& tq& tp\\ 1& 1& t& t(q-1)-1& t(p-1)-1\end{array}\right)$$where $t=p^{\alpha -1}{q}^{\beta -1}$.

Proof.

Let $n=p^{\alpha }{q}^{\beta }$. Then the proper divisors of n are of the form $p^i{q}^j$, where $0\le i\le \alpha ,0\le j\le \beta$. Note that $$\begin{array}{c}V({\Gamma }_U({\mathbb{Z}}_n))=({\mathcal{A}}_p\cup {\mathcal{A}}_{p^2}\cup \cdots \cup {\mathcal{A}}_{p^{\alpha }})\cup ({\mathcal{A}}_q\cup {\mathcal{A}}_{q^2}\\ \times \cup \cdots \cup {\mathcal{A}}_{q^{\beta }})\cup (\underset{j=1}{\overset{\beta }{\cup }}{\mathcal{A}}_{p{q}^j})\cup (\underset{j=1}{\overset{\beta }{\cup }}{\mathcal{A}}_{p^2{q}^{j_1}})\\ \times \cup \cdots \cup (\underset{j=1}{\overset{\beta -1}{\cup }}{\mathcal{A}}_{p^{\alpha }{q}^j}).\end{array}$$

Let $x_1\in {\mathcal{A}}_{p^{i_1}},x_2\in {\mathcal{A}}_{p^{i_2}}$ and $y_1\in {\mathcal{A}}_{q^{j_1}},y_2\in {\mathcal{A}}_{q^{j_2}}$. Then by Lemma 6.2, we get $x_1\sim x_2$ and $y_1\sim y_2$ in ${\Gamma }_U({\mathbb{Z}}_n)$. Also, note that for $x\in {\mathcal{A}}_{p^i}$ and $y\in {\mathcal{A}}_{q^j}$, we have $x\nsim y$. Further, for any $x\in {\mathcal{A}}_{p^i{q}^j}$ and $y\in {\mathcal{A}}_{p^i}\cup {\mathcal{A}}_{q^j}$ such that $1\le i\le \alpha ,1\le j\le \beta$ with $i+j\ne \alpha +\beta$, we have $x\sim y$ in ${\Gamma }_U({\mathbb{Z}}_n)$ (cf. Lemma 6.2). Also, for any proper divisor $p^i{q}^j$ $(i,j\ne 0)$ of n, we obtain $x\sim y$ in ${\Gamma }_U({\mathbb{Z}}_n)$. Next, we have $$\begin{array}{c}\sum _{i=1}^{\alpha }\left|{\mathcal{A}}_{p^i}\right|=\left|{\mathcal{A}}_p\right|+\left|{\mathcal{A}}_{p^2}\right|+\cdots +\left|{\mathcal{A}}_{p^{\alpha }}\right|\\ =\varphi (p^{\alpha -1}{q}^{\beta })+\varphi (p^{\alpha -2}{q}^{\beta })+\cdots +\varphi (q^{\beta })\\ =p^{\alpha -1}{q}^{\beta -1}(q-1)=t(q-1)\end{array}$$

Similarly, we obtain $$\sum _{j=1}^{\beta }\left|{\mathcal{A}}_{q^j}\right|=p^{\alpha -1}{q}^{\beta -1}(p-1)=t(p-1)$$

Also, we have $0\sim x$, for each $x\in {\Gamma }_U({\mathbb{Z}}_n)$. Note that the graph $${\Gamma }_U({\mathbb{Z}}_n)\cong K_t\vee (K_{t(q-1)}\cup K_{t(p-1)}).$$

By Theorem 6.12, the characteristic polynomial of the Laplacian matrix of $K_{t(q-1)}\cup K_{t(p-1)}$ is $$\begin{array}{c}\mu (K_{t(q-1)}\cup K_{t(p-1)},x)=x{(x-t(q-1))}^{t(q-1)-1}\\ \times x{(x-t(p-1))}^{t(p-1)-1}.\end{array}$$

Consequently, by Theorem 6.11, the characteristic polynomial of the Laplacian matrix of $K_t\vee (K_{t(q-1)}\cup K_{t(p-1)})$ is $$\begin{array}{c}\mu (K_t\vee (K_{t(q-1)}\cup K_{t(p-1)}),x)=x(x-{(t(p+q-1))}^t\\ \times {(x-tq)}^{t(q-1)-1}\times (x-t){(x-tp)}^{t(p-1)-1}.\end{array}$$

Therefore, the Laplacian eigenvalues of ${\Gamma }_U({\mathbb{Z}}_n)$ are 0, t, $t(p+q-1)$, tq, and tp with multiplicities 1, 1, t, $t(q-1)-1$ and $t(p-1)-1$, respectively. Thus, the result holds. □

6.2.2 Normalized Laplacian spectrum of ${\Gamma }_U({\mathbb{Z}}_n)$

In this subsection, we investigate the normalized Laplacian eigenvalues of the graph ${\Gamma }_U({\mathbb{Z}}_n)$ for $n=p^{\alpha }{q}^{\beta }$. Note that ${\Gamma }_U({\mathbb{Z}}_{p^{\alpha }{q}^{\beta }})=P_3[K_{\left|M_1\right|},K_{\left|M_2\right|},K_{\left|M_3\right|}]$, where $M_1=(p)\setminus (pq),M_2=(pq)$ and $M_3=(q)\setminus (pq)$. Also, $\left|M_1\right|={\sum }_{i=1}^{\alpha }\left|{\mathcal{A}}_{p^i}\right|=p^{\alpha -1}{q}^{\beta }-p^{\alpha -1}{q}^{\beta -1},\left|M_2\right|=p^{\alpha -1}{q}^{\beta -1}$ and $\left|M_3\right|={\sum }_{j=1}^{\beta }\left|{\mathcal{A}}_{q^j}\right|=p^{\alpha }{q}^{\beta -1}-p^{\alpha -1}{q}^{\beta -1}$.

Example 6.16.

Let p be a prime and α be a positive integer. Then ${\Gamma }_U({\mathbb{Z}}_{p^{\alpha }})\cong K_{p^{\alpha -1}}$. Therefore, the normalized Laplacian spectrum of ${\Gamma }_U({\mathbb{Z}}_{p^{\alpha }})$ is $\left(\begin{array}{cc}0& \frac{p^{\alpha -1}}{p^{\alpha -1}-1}\\ 1& p^{\alpha -1}-1\end{array}\right)$.

Example 6.17.

If $n=p^{2}q$, then ${\Gamma }_U({\mathbb{Z}}_n)\cong P_3[K_{pq-p},K_p,K_{p^2-p}]$. By Lemmas 6.13 and 6.14, the eigenvalues of ${\Gamma }_U({\mathbb{Z}}_n)$ are $\frac{pq}{pq-1},\frac{p(p+q-1)}{p(p+q-1)-1}$ and $\frac{p^2}{p^2-1}$ with multiplicities $pq-p-1,p-1$ and $p^2-p-1$, respectively. The remaining 3 eigenvalues are the eigenvalues of the matrix $$\left[\begin{array}{ccc}\frac{p}{pq-1}& \frac{-p}{\sqrt{(pq-1)(p(p+q-1)-1)}}& 0\\ \frac{-p(q-1)}{\sqrt{(pq-1)(p(p+q-1)-1)}}& \frac{p(p+q-2)}{p(p+q-1)-1}& \frac{-p(p-1)}{\sqrt{(p^2-1)(p(p+q-1)-1)}}\\ 0& \frac{-p}{\sqrt{(p^2-1)(p(p+q-1)-1)}}& \frac{p}{p^2-1}\end{array}\right].$$

Theorem 6.18.

The normalized Laplacian eigenvalues of ${\Gamma }_U({\mathbb{Z}}_{p^{\alpha }{q}^{\beta }})$ consists of the eigenvalues $\frac{\left|M_1\right|+\left|M_2\right|}{\left|M_1\right|+\left|M_2\right|-1}$ with multiplicity $\left|M_1\right|-1,\frac{\left|M_1\right|+\left|M_2\right|+\left|M_3\right|}{\left|M_1\right|+\left|M_2\right|+\left|M_3\right|-1}$ with multiplicity $\left|M_2\right|-1$ and $\frac{\left|M_2\right|+\left|M_3\right|}{\left|M_2\right|+\left|M_3\right|-1}$ with multiplicity $\left|M_3\right|-1$ and the remaining 3 eigenvalues are the eigenvalues of the matrix $$\left[\begin{array}{ccc}\frac{\left|M_2\right|}{\left|M_1\right|+\left|M_2\right|-1}& \frac{-\left|M_2\right|}{\sqrt{(|M_1|+|M_2|-1)(|M_1|+|M_2|+|M_3|-1)}}& 0\\ \frac{-\left|M_1\right|}{\sqrt{(|M_1|+|M_2|+|M_3|-1)(|M_1|+|M_2|-1)}}& \frac{\left|M_1\right|+\left|M_3\right|}{\left|M_1\right|+\left|M_2\right|+\left|M_3\right|-1}& \frac{-\left|M_3\right|}{\sqrt{(|M_1|+|M_2|+|M_3|-1)(|M_2|+|M_3|-1)}}\\ 0& \frac{-\left|M_2\right|}{\sqrt{(|M_2|+|M_3|-1)(|M_1|+|M_2|+|M_3|-1)}}& \frac{\left|M_2\right|}{\left|M_2\right|+\left|M_3\right|-1}\end{array}\right]$$where, $\left|M_1\right|=p^{\alpha -1}{q}^{\beta }-p^{\alpha -1}{q}^{\beta -1},\left|M_2\right|=p^{\alpha -1}{q}^{\beta -1}$ and $\left|M_3\right|=p^{\alpha }{q}^{\beta -1}-p^{\alpha -1}{q}^{\beta -1}$.

Proof.

Note that ${\Gamma }_U({\mathbb{Z}}_{p^{\alpha }{q}^{\beta }})=\Gamma [{\Gamma }_1,{\Gamma }_2,{\Gamma }_3]$, where $\Gamma =P_3,{\Gamma }_1=K_{\left|M_1\right|},{\Gamma }_2=K_{\left|M_2\right|}$ and ${\Gamma }_3=K_{\left|M_3\right|}$. In view of Lemma 6.14, we have $r_i=\left|M_i\right|-1$ for each i = 1, 2, 3. By Lemma 6.13, for $1\le i\le 3$, the adjacency spectrum of $K_{\left|M_i\right|}$ is given by $(\begin{array}{cc}\left|M_i\right|-1& -1\\ 1& \left|M_i\right|-1\end{array})$.

Let $\{v_1,v_2,v_3\}$ is the vertex set of P₃ corresponding to the graph ${\Gamma }_1,{\Gamma }_2,{\Gamma }_3$. Since ${\Gamma }_U({\mathbb{Z}}_n)\cong K_{\left|M_2\right|}\vee (K_{\left|M_1\right|}\cup K_{\left|M_3\right|})$, we have $$\begin{array}{c}{\alpha }_1=\sum _{v_j\in N_{\Gamma }(v_1)}^{}{n}_i=\left|{\Gamma }_2\right|=\left|M_2\right|,\\ {\alpha }_2=\sum _{v_j\in N_{\Gamma }(v_2)}^{}{n}_i=\left|{\Gamma }_1\right|+\left|{\Gamma }_3\right|=\left|M_1\right|+\left|M_3\right|,\\ {\alpha }_3=\sum _{v_j\in N_{\Gamma }(v_3)}^{}{n}_i=\left|{\Gamma }_2\right|=\left|M_2\right|.\end{array}$$

Now by Lemma 6.14, the normalized Laplacian eigenvalues of ${\Gamma }_U({\mathbb{Z}}_{p^{\alpha }{q}^{\beta }})$ are given by $1-\frac{1}{r_i+{\alpha }_i}{\lambda }_{ik}({\Gamma }_i)$, for i = 1, 2, 3 and $k=2,3,\dots ,n_i$. Since ${\lambda }_{ik}=-1$, where i = 1, 2, 3 and $2\le k\le n_i$, by Lemma 6.14, the normalized Laplacian eigenvalues of ${\Gamma }_U({\mathbb{Z}}_n)$ are

$\frac{\left|M_1\right|+\left|M_2\right|}{\left|M_1\right|+\left|M_2\right|-1},1+\frac{1}{\left|M_1\right|+\left|M_2\right|+\left|M_3\right|-1}$ and $\frac{\left|M_2\right|+\left|M_3\right|}{\left|M_2\right|+\left|M_3\right|-1}$ with multiplicities $\left|M_1\right|-1,\left|M_2\right|-1$ and $\left|M_3\right|-1$, respectively.

Since $a_{12}=a_{21}=a_{23}=a_{32}=1,a_{13}=a_{31}=0,{\alpha }_1=\left|M_2\right|,{\alpha }_2=\left|M_1\right|+\left|M_3\right|,{\alpha }_3=\left|M_2\right|$ and $r_1=\left|M_1\right|-1,r_2=\left|M_2\right|-1,r_3=\left|M_3\right|-1$, by Lemma 6.14 the remaining 3 eigenvalues are the eigenvalues of the following matrix. $$\left[\begin{array}{ccc}\frac{\left|M_2\right|}{\left|M_1\right|+\left|M_2\right|-1}& \frac{-\left|M_2\right|}{\sqrt{(|M_1|+|M_2|-1)(|M_1|+|M_2|+|M_3|-1)}}& 0\\ \frac{-\left|M_1\right|}{\sqrt{(|M_1|+|M_2|+|M_3|-1)(|M_1|+|M_2|-1)}}& \frac{\left|M_1\right|+\left|M_3\right|}{\left|M_1\right|+\left|M_2\right|+\left|M_3\right|-1}& \frac{-\left|M_3\right|}{\sqrt{(|M_1|+|M_2|+|M_3|-1)(|M_2|+|M_3|-1)}}\\ 0& \frac{-\left|M_2\right|}{\sqrt{(|M_2|+|M_3|-1)(|M_1|+|M_2|+|M_3|-1)}}& \frac{\left|M_2\right|}{\left|M_2\right|+\left|M_3\right|-1}.\end{array}\right]$$□

Acknowledgments

The authors are deeply grateful to the referees for the careful reading of the manuscript and helpful suggestions.

Additional information

Funding

The first author gratefully acknowledges for providing financial support to CSIR (09/719(0093)/2019-EMR-I) government of India. The second author sincerely acknowledges for providing financial support to Birla Institute of Technology and Science (BITS) Pilani, India.