Metric dimension of ideal-intersection graph of the ring Zn

Abstract

Metric Dimension of a simple connected graph is the minimum number of vertices those are used to identify each vertex of the graph uniquely using distance code. In this paper, we determine metric dimension of ideal-intersection graph for the ring ${\mathbb{Z}}_n,$ where n being a positive integer.

Keywords:

• Ideal-intersection graph
• resolving set
• metric dimension

AMSC 2010:

• 05C12
• 05C05
• 05C90
• 05C76

1. Introduction

The problem of placing a minimum number of stations (sonar/loran detecting devices) in a network so that the position of every vertex in the network can be uniquely described in terms of graph theoretic distances. This motivates the study of graph theoretic parameter metric dimension of a connected graph G. The Metric dimension problem was introduced by Slater [10] (independently Harary and Melter [7]) and further studied in [1–5, 8, 9]. Application of resolving set and metric dimension arise in many various platforms such as Robot Navigation [8], Digitization of Image [11], Network Optimization [3], Mastermind game [5] and chemistry and Drug Design [4].

For an ordered subset $S=\{w_1,w_2,\dots ,w_k\}\subset$ V(G) and a vertex v of G, the code of v with respect to S is a k-vector given by $\mathit{cod}{e}_S(v)=(d(v,w_1),d(v,w_2),\dots ,d(v,w_k)).$ $\mathit{Cod}{e}_S(v)$ is also called the metric representation of v with respect to S. If $\mathit{cod}{e}_S(u)$ = $\mathit{cod}{e}_S(v)$ implies that u = v for all pairs u, v of vertices of G, then S is called a resolving set for the graph G. The metric dimension of graph G is the minimum cardinality of a resolving set for G and it is denoted by $\beta (G).$ Throughout this paper, $\mathit{cod}{e}_S(v)$ is simply denoted by $\mathit{code}‐v.$ In this paper, we consider the more convenient intersection graphs namely, ideal intersection graph for the ring ${\mathbb{Z}}_n$ of integers modulo n and determine the metric dimension of $G({\mathbb{Z}}_n)$ for all values of n.

2. Preliminaries and definition

Definition 2.1.

For a commutative ring R, ideal-intersection graph is a simple graph whose vertices are non-zero proper ideals of the ring R and two vertices (ideals) are adjacent if their intersection is also a non-zero (proper) ideal of R. Throughout this paper, G(R) denotes ideal-intersection graph of the ring R.

For a given positive integer n, define P(n) be the set of all primes that are used to decompose the integer n. For example, if $n=p_1^{{\alpha }_1},p_2^{{\alpha }_2},\dots ,p_r^{{\alpha }_r},$ then $P(n)=\{p_1,p_2,\dots ,p_r\}.$ Throughout this paper, we denote $<m>$ be the ideal generated by $\overline{m}$ in the ring ${\mathbb{Z}}_n.$

Lemma 2.1.

For any positive integer $n=p_1^{{\alpha }_1},p_2^{{\alpha }_2},\dots ,p_r^{{\alpha }_r}$, every ideal of the ring ${\mathbb{Z}}_n$ is of the forms $I=<p_1^{{\beta }_1},p_2^{{\beta }_2},\dots ,p_r^{{\beta }_r}>$, where β_i’s are integers with $0\le {\beta }_i\le {\alpha }_i.$

Next lemma gives the number of vertices of the ideal intersection graph $G({\mathbb{Z}}_n).$

Lemma 2.2.

For $n=p_1^{{\alpha }_1},p_2^{{\alpha }_2},\dots ,p_r^{{\alpha }_r}$, the ideal-intersection graph $G({\mathbb{Z}}_n)$ has $\prod _{1\le i\le r}({\alpha }_i+1)-2$ vertices.

Proof.

Lemma 2.1 gives that every ideal I of ${\mathbb{Z}}_n$ is of the form $I=<p_1^{{\beta }_1},p_2^{{\beta }_2},\dots ,p_r^{{\beta }_r}>,$ where $0\le {\beta }_i\le {\alpha }_i.$ There are total $\prod _{1\le i\le r}({\alpha }_i+1)$ ideals of the ring ${\mathbb{Z}}_n.$ Now if ${\beta }_i={\alpha }_i$ for all $i=1,2,\dots ,r,$ then $I=<0>$ and if ${\beta }_i=0$ for all $i=1,2,\dots ,r,$ then $I={\mathbb{Z}}_n.$ As vertices of $G({\mathbb{Z}}_n)$ are the nonzero proper ideals of ${\mathbb{Z}}_n,$ so $|V(G({\mathbb{Z}}_n))|=\prod _{1\le i\le r}({\alpha }_i+1)-2.$

Definition 2.2.

For any ideal $I=<p_1^{{\beta }_1},p_2^{{\beta }_2},\dots ,p_r^{{\beta }_r}>$ of the ring ${\mathbb{Z}}_n$ with $n=p_1^{{\alpha }_1},p_2^{{\alpha }_2},\dots ,p_r^{{\alpha }_r},$ define a set $L(I)=\{p_i:{\beta }_i={\alpha }_i\}$ and called it by level set for I. The ideal I is called $i‐th$ level ideal if cardinality of L(I) is i. Also we define $L^{\prime }(I)=\{p_i:{\beta }_i\ne {\alpha }_i\}.$ It is clear to observe that for a fixed ideal I, $L(I)\subset P(n)$ and $L\prime (I)$ is the complement of L(I) in P(n), i.e., $L(I)\cup L^{\prime }(I)=P(n)$ with $L\prime (I)\cap L(I)=\varphi .$

Now we give some properties of the level set L(I) for an ideal I in the following.

Proposition 2.1.

Let $n=p_1^{{\alpha }_1},p_2^{{\alpha }_2},\dots ,p_r^{{\alpha }_r}$. Then for the ring ${\mathbb{Z}}_n$, we have the following

1. $I=<0>=<p_1^{{\alpha }_1},p_2^{{\alpha }_2},\dots ,p_r^{{\alpha }_r}>$, if and only if $L(I)=P(n),$ where $P(n)=\{p_1,p_2,\dots ,p_r\}.$

2. $I=<p_1^{{\beta }_1},p_2^{{\beta }_2},\dots ,p_r^{{\beta }_r}>$ with ${\beta }_i\ne {\alpha }_i$ for all i, if and only if $L(I)=\varphi .$

Lemma 2.3.

For any two ideals I and J of the ring ${\mathbb{Z}}_n,L(I\cap J)=L(I)\cup L(J).$

Proof.

By Lemma 2.1, we may assume $I=<p_1^{{\beta }_1},p_2^{{\beta }_2},\dots ,p_r^{{\beta }_r}>$ and $J=<p_1^{{\gamma }_1},p_2^{{\gamma }_2},\dots ,p_r^{{\gamma }_r}>.$ Then $I\cap J=<p_1^{\max \{{\beta }_1,{\gamma }_1\}},p_2^{\max \{{\beta }_2,{\gamma }_2\}},\dots ,p_r^{\max \{{\beta }_r,{\gamma }_r\}}>.$ Now from Definition 2.2, $L(I\cap J)=\{p_i:\max \{{\beta }_i,{\gamma }_i\}={\alpha }_i\}=\{p_i:\mathrm{ }\text{either}\mathrm{ }{\beta }_i={\alpha }_i\mathrm{ }\text{or}\mathrm{ }{\gamma }_i={\alpha }_i\}=L(I)\cup L(J).$ □

Recall that for a positive integer n, P(n) denotes the set of all primes that are used to decompose n. From here to onward, we denote $|P(n)|$ by r.

Theorem 2.1.

Two vertices I and J in $G({\mathbb{Z}}_n)$ are non-adjacent if and only if $|L(I\cap J)|=r.$

Proof.

Since I and J are non zero proper ideals, their intersection ideal is also proper ideal but it may be zero. Definition 2.1 implies that two vertices I and J are non-adjacent if and only if $<I\cap J>=<0>.$ Then by Proposition 2.1, $<I\cap J>=<0>$ if and only if $L(I\cap J)=P(n)$ and hence $|L(I\cap J)|=|P(n)|.$ □

Corollary 2.1.

Two vertices I and J in $G({\mathbb{Z}}_n)$ are adjacent if and only if $|L(I\cap J)|<r.$

Corollary 2.2.

Every zero level ideal is adjacent to every vertex of $G({\mathbb{Z}}_n).$

Proof.

Let I be an zero level ideal and $J\in V(G({\mathbb{Z}}_n))\setminus \left\{I\right\}$ be an arbitrary vertex. Then $L(I)\cap L(J)=L(J)$ and hence $|L(I)\cap L(J)|=|L(J)|\le r-1.$ So I is adjacent to J in $G({\mathbb{Z}}_n).$ □

Corollary 2.3.

Two vertices (ideals) I and J with same level set in $G({\mathbb{Z}}_n)$ are adjacent.

Now our aim is to find a partition of the vertex set by defining an equivalence relation on $V(G({\mathbb{Z}}_n)).$

Definition 2.3.

We define a relation ρ on the set of vertices of $G({\mathbb{Z}}_n)$ as follows: for two vertices I and J of $G({\mathbb{Z}}_n),I\rho J$ if and only if $L(I)=L(J).$

Clearly, the relation ρ defined above is an equivalence relation and so the vertex set $V(G({\mathbb{Z}}_n))$ can be partitioned into equivalence classes.

Definition 2.4.

For a vertex I (ideal) of $G({\mathbb{Z}}_n),$ let us define the class of I by the set $\{J\in V(G({\mathbb{Z}}_n)):J\rho I\}$ and we denote it by $[I].$ For an $i\text{th}$ level ideal I, we call the class $[I]$ as $i\text{th}$ level ideal class. It is clear to observe that for each i, there are $\left(\begin{array}{c}r\\ i\end{array}\right)$ numbers of $i\text{th}$ level ideal classes. We denote the set of all $i\text{th}$ level ideals by A_i. Some ideal classes may contain more than one elements. We call the ideal classes containing exactly one element (vertex/ideal) by one element ideal class, otherwise, many element ideal class.

Lemma 2.4.

For the graph $G({\mathbb{Z}}_n)$, we have the following

1. The diameter of $G({\mathbb{Z}}_n)$ is 2.

2. Every distinct pair of classes preserve the distances, i.e., for two ideals $I_1\in [I]$ and $J_1\in [J],d(I_1,J_1)=1 or 2$ according as $d(I,J)=1$ and $d(I,J)=2.$

3. Each ideal class $[I]$ forms a clique in $G({\mathbb{Z}}_n).$

Proof.

(a) Since every zero level element (if exists) is adjacent to all others elements of $G({\mathbb{Z}}_n)$ and $(r-1)$-th level elements are not adjacent to each other, so the result is true when $G({\mathbb{Z}}_n)$ contains at least one zero level element. Now we assume that the graph $G({\mathbb{Z}}_n)$ does not contains any zero level element. From Corollary 2.1, $d(I,J)\le 2$ for any two distinct ideals I and J with $1\le |L(I)|,|L(J)|\le r-2.$ Let I and J be two arbitrary elements from $(r-1)$ th level with level sets L(I) and L(J) respectively. Since both L(I) and L(J) contains $(r-1)$ elements from P(n) and $|P(n)|=r,L(I)\cap L(J)\ne \varphi .$ Let $p_i\in L(I)\cap L(J).$ Again there exists an one level element K with level set $L(K)=\left\{p_i\right\}.$ Therefore by Theorem 2.1, $d(I,J)=2.$ Thus we obtain our result.

(b) From given conditions, $L(I_1)=L(I)$ and $L(J_1)=L(J).$ First we assume $d(I,J)=1.$ Then by Corollary 2.1 and Lemma 2.3, I and J are adjacent if only if $|L(I_1)|+|L(J_1)|-|L(I_1)\cap L(J_1)|<r,$ which implies and implied by I₁ and J₁ are adjacent. Now if I and J are not adjacent, then $d(I,J)=2$ as the diameter of $G({\mathbb{Z}}_n)$ is 2. From Theorem 2.1, $d(I,J)=2$ if and only if $|L(I_1)|+|L(J_1)|-|L(I_1)\cap L(J_1)|=r,$ which implies and implied by $d(I_1,J_1)=2.$

(c) If $[I]$ is one element ideal class, then it is obvious. Again if $[I]$ is a many element ideal class, then for two distinct $I_1,I_2\in [I],$ we have $|L(I_1\cap I_2)|=|L(I_1)|+|L(I_2)|-|L(I_1)\cap L(I_2)|=|L(I_1)|=|L(I_2)|<r,$ which implies that I₁ and I₂ are adjacent by Corollary 2.1. Thus $[I]$ form a complete subgraph of $G({\mathbb{Z}}_n).$ □

Definition 2.5.

[6] Let u be a vertex of a graph G. The open neighborhood of u is a set $N(u):=\{v\in V(G):v\mathrm{ }\text{is}\mathrm{ }\text{adjacent}\mathrm{ }\text{to}\mathrm{ }u\},$ and the closed neighborhood of u is a set $N[u]:=N(u)\cup \left\{u\right\}.$ Two distinct vertices u, v are adjacent twins if $N[u]=N[v],$ and non-adjacent twins if $N(u)=N(v).$ For a graph G, a set $T\subseteq V(G)$ is called a twin set of G if v, w are twins in G for every pair of distinct vertices $v,w\in T.$

Lemma 2.5.

[6] If u, v are twins in a connected graph G, then $d(u,x)=d(v,x)$ for every vertex $x\in V(G)\setminus \{u,v\}.$

Lemma 2.6.

[6] If $T\subset V(G)$ is a twin set with cardinality $\left|T\right|$, then any resolving set must contains $(|T|-1)$ elements of T.

Lemma 2.7.

Each many element ideal class in $G({\mathbb{Z}}_n)$ is a twin set.

Proof.

Let $[I]$ be a many element ideal class and $I_1,I_2\in [I]$ be any two elements. $N(I)=N(I_1)=N(I_2)$ as $d(J,I)=d(J,I_1)=d(J,I_2)$ (by Lemma 2.4), where J is arbitrary. Thus every elements of $[I]$ have same neighborhood. Hence $[I]$ is a twin set. □

3. Metric dimension of $G({\mathbb{Z}}_{p_1,p_2,p_3,\dots ,p_r})$

In this section, we determine the exact value of the metric dimension of $G({\mathbb{Z}}_{p_1,p_2,p_3,\dots ,p_r}).$ Recall that for $n=p_1,p_2,p_3,\dots ,p_r,$ every ideal class is an one element ideal class. The following result is due to Khuller et al. [8].

Lemma 3.1.

[8] Let G be a finite graph with diameter d and metric dimension β. Then G has maximum $d^{\beta }+\beta$ vertices.

In the following theorem, we give the metric dimension for $G({\mathbb{Z}}_n),$ when $n=p_1,p_2,p_3,\dots ,p_r.$

Theorem 3.1.

For any integer $r\ge 4$, the metric dimension of $G({\mathbb{Z}}_{p_1,p_2,p_3,\dots ,p_r})$ is r.

Proof.

Let $\beta (G({\mathbb{Z}}_n))=m$ and if possible, we assume m < r. Then applying Lemma 3.1, the graph $G({\mathbb{Z}}_n)$ can have at most $2^m+m$ vertices as the diameter of $G({\mathbb{Z}}_n)$ is 2. Lemma 2.2 gives that $G({\mathbb{Z}}_n)$ has $2^r-2$ vertices. Since $r\ge 4$ and m < r, we have $2^r-2>2^{r-1}+r-1\ge 2^m+m.$ Thus we arrive a contradiction. Therefore, $\beta (G({\mathbb{Z}}_n))\ge r.$ Now we show $A_{r-1}=\{I:L(I)=P(n)\setminus \{p_i\},1\le i\le r\}$ is a resolving set for $G({\mathbb{Z}}_{p_1,p_2,p_3,\dots ,p_r}).$ Let $I,J\in V(G({\mathbb{Z}}_{p_1,p_2,\dots ,p_r}))\setminus A_{r-1}$ be two distinct ideals with level sets L(I) and L(J), respectively. Without loss of generality, we may assume $|L(J)|\le |L(I)|.$ Since I and J are distinct ideals, there exists at least one $p_i\in P(n)$ such that $p_i\in L(I)$ but $p_i\notin L(J)$ even if it is the case $|L(J)|=|L(I)|.$ Let $K\in A_{r-1}$ with $L(K)=P(n)\setminus \left\{p_i\right\}.$ Now by Theorem 2.1 and Corollary 2.1, $d(K,I)=1$ and $d(K,J)=2.$ Thus K resolves I and J. Hence $A_{r-1}$ form a resolving set. Therefore $\beta (G({\mathbb{Z}}_{p_1,p_2,\dots ,p_r}))=r.$ □

In the following theorem, we show that the graph $G({\mathbb{Z}}_{p_1,p_2,p_3,\dots ,p_r})$ has unique metric basis, namely, $A_{r-1}.$

Theorem 3.2.

For $r\ge 4,G({\mathbb{Z}}_{p_1,p_2,p_3,\dots ,p_r})$ has unique metric basis.

Proof.

Let B be an another metric basis other than $A_{r-1}.$ Since metric dimension of $G({\mathbb{Z}}_{p_1,p_2,\dots ,p_r})$ is r, so $\left|B\right|=r.$ If B = A₁, then codes of each elements of $A_2,A_3,\dots ,A_{r-2}$ are same with respect to A₁ as every element of A₁ is adjacent to any element of $A_2,A_3,\dots ,A_{r-2}$ by Corollary 2.1. Again if $B\subset {\cup }_{i=2}^{r-2}{A}_i,$ then also codes of each elements of $A_{r-1}$ are same with respect to B as $d(v_i,v)=d(v_j,v)=2$ where $v_i,v_j\in A_{r-1}$ and v is an arbitrary element in ${\cup }_{i=2}^{r-2}{A}_i.$ Now let $B\subset {\cup }_{i=1}^{r-2}{A}_i.$ Then we consider the following two cases depending on the number of elements in $|B\cap A_1|.$

Case-1: $|B\cap A_1|\le (r-2).$ In this case $\left|A_1\setminus B\right|\ge 2$ and the codes of all elements in $A_1\setminus B$ are same namely, $(1,1,\dots ,1).$

Case-2: $|B\cap A_1|=(r-1).$ Here exactly one element is in $B\setminus A_1$ and this element must be in ${\cup }_{i=1}^{r-2}{A}_i$ as $B\subset {\cup }_{i=1}^{r-2}{A}_i.$ Say this unique element of $B\setminus A_1$ is in A_i, where $2\le i\le (r-2).$ Then any two element of A₂ with condition that their level sets have non empty intersection with the level set of the remaining element of B have same code as they are at distance 1 from all elements of B.

From above it is clear that B must have intersection with $A_{r-1}.$ Since $B\ne A_{r-1}$ then there exists at lest one element of $A_{r-1}$ such that it is not in B. Suppose that $1\le m<r$ number of elements of $A_{r-1}$ are not in B. These m elements of B are from $A_1,A_2,A_3,\dots ,A_{r-2}.$ Since $1\le m<r$ and $r\ge 4,(\begin{array}{c}r\\ 2\end{array})-m\ge 2.$ Thus there are $(\begin{array}{c}r\\ 2\end{array})-m$ number of elements of A₂ having same codes because using Theorem 2.1 and Corollary 2.1 we have $$d(u,v_i)=\{\begin{array}{cc}2,\hfill & v_i\in A_{r-1}\mathrm{ }\text{or}\mathrm{ }{A}_{r-2};\hfill \\ 1,\hfill & \text{otherwise}.\hfill \end{array}$$ for any $u\in A_2\setminus B.$ This proves that $B=A_{r-1}$ and so $A_{r-1}$ is the only basis for $G({\mathbb{Z}}_{p_1,p_2,\dots ,p_r}).$ □

Theorem 3.1 gives the metric dimension for $G({\mathbb{Z}}_{p_1,p_2,p_3,\dots ,p_r}),$ where p_i are distinct primes and $r\ge 4.$ Now we determine the metric dimension for $G({\mathbb{Z}}_{p_1{p}_2{p}_3}),$ where $p_1,p_2,p_3$ are distinct primes.

Theorem 3.3.

For distinct primes p₁, p₂ and p₃, the metric dimension of $(G({\mathbb{Z}}_{p_1{p}_2{p}_3})$ is 2.

Proof.

The vertex set of $G({\mathbb{Z}}_{p_1{p}_2{p}_3})$ is given by $V(G({\mathbb{Z}}_{p_1{p}_2{p}_3}))=\{<p_1>,<p_2>,<p_3>,<p_1{p}_2>,<p_2{p}_3>,<p_1{p}_3>\}.$ Here $S=\{<p_1{p}_2>,<p_1{p}_3>\}$ forms a resolving set for that graph, as $\mathit{code}‒<p_1>=(1,1),\mathit{code}‒<p_2>=(1,2),\mathit{code}‒<p_3>=(2,1)$ and $\mathit{code}-<p_2{p}_3>=(2,2).$ Thus we say that metric dimension is at most 2. Now the graph $G({\mathbb{Z}}_{p_1{p}_2{p}_3})$ contains three ideal of level 1 and three ideals of level 2. No 1-level ideal forms a resolving set as the codes of others two ideal of level 1 are same. Again the 2-level ideal $\{<p_1{p}_2>\}$ is not a resolving set as the codes of $<p_1>$ and $<p_2>$ are same. Due to the similar reasons $\{<p_1{p}_3>\}$ and $\{<p_2{p}_3>\}$ can not form a resolving set separately. Thus we say that $\beta (G({\mathbb{Z}}_{p_1{p}_2{p}_3}))\ge 2.$ Also in above we show that $S=\{<p_1{p}_2>,<p_1{p}_3>\}$ is a resolving set. Therefore, $\beta (G({\mathbb{Z}}_{p_1{p}_2{p}_3}))=2.$ □

Recall that $n=p_1^{{\alpha }_1},p_2^{{\alpha }_2},\dots ,p_r^{{\alpha }_r}$ where p_i are prime and α_i are positive integers. In the next section, we assume that some α_i are equal to 1 and others are greater than 1. For the sake of problem, let us consider first consecutive s numbers of α_i’s are equal to one and rest are greater than one.

4. Metric dimension of $G({\mathbb{Z}}_{p_1{p}_2\dots p_s{p}_{s+1}^{{\alpha }_{s+1}}\dots p_r^{{\alpha }_r}})$ where ${\alpha }_i\ge 2$

For $n=p_1{p}_2\dots p_s{p}_{s+1}^{{\alpha }_{s+1}}\dots p_r^{{\alpha }_r},$ the graph $G({\mathbb{Z}}_n)$ consist of $2^s-1$ numbers of one element ideal classes and the remaining $2^r-2^s$ numbers of many elements ideal classes.

Example 4.1.

For the graph $G({\mathbb{Z}}_{p_1{p}_2{p}_3^2{p}_4^2}),[<p_3^2{p}_4^2>],[<p_3^2{p}_4^2{p}_1>],[<p_3^2{p}_4^2{p}_2>]$ are one element ideal classes whereas some many element ideal classes are $[<p_3>]=\{<p_3>,<p_4>,<p_3{p}_4>\};[<p_2>]=\{<p_2>,<p_2{p}_3{p}_4>,<p_2{p}_3>,<p_2{p}_4>\};[<p_3^2>]=\{<p_3^2>,<p_3^2{p}_4>\};[<p_4^2>]=\{<p_4^2>,<p_3{p}_4^2>\}.$

In the following theorem, we give a lower bound of metric dimension for $G({\mathbb{Z}}_{p_1{p}_2\dots p_s{p}_{s+1}^{{\alpha }_{s+1}}\dots p_r^{{\alpha }_r}}).$

Theorem 4.1.

For $n=p_1{p}_2\dots p_s{p}_{s+1}^{{\alpha }_{s+1}}\dots p_r^{{\alpha }_r}$, the metric dimension of $G({\mathbb{Z}}_n)$ satisfies $$\beta (G({\mathbb{Z}}_n))\ge 2^s({\alpha }_{s+1}+1)({\alpha }_{s+2}+1)\dots ({\alpha }_r+1)+s-2^r-1.$$

Proof.

Let R be a minimal resolving set for $G({\mathbb{Z}}_n).$ In $V(G({\mathbb{Z}}_n)),$ there are $2^r-2^s$ many element ideal classes and they form twin sets $T_1,\dots ,T_{2^r-2^s}$ due to Lemma 2.7. By Lemma 2.6, $|R\cap T_i|\ge \left|T_i\right|-1$ for all $i=1,2,\dots ,2^r-2^s.$ Therefore $\left|R\right|\ge \sum (|T_i|-1)=2^s({\alpha }_{s+1}+1)({\alpha }_{s+2}+1)\dots ({\alpha }_r+1)-2^r-1.$ We show that $\left|R\right|\ge 2^s({\alpha }_{s+1}+1)({\alpha }_{s+2}+1)\dots ({\alpha }_r+1)+s-2^r-1.$ If possible, let $\left|R\right|=2^s({\alpha }_{s+1}+1)({\alpha }_{s+2}+1)\dots ({\alpha }_r+1)+l-2^r-1,$ where $0\le l\le s-1.$ Let $B\subseteq R\cap T\subseteq R$ be a set such that $|B\cap T_i|=\left|T_i\right|-1$ for all $i=1,2,\dots ,2^r-2^s.$ Thus $B\subseteq R$ and $\left|B\right|=\sum (|T_i|-1).$ Let $S=\{I:I\in T\setminus B,L(I)=\{p_i\},i=1,\dots ,s\}$ and $C=\{I:L(I)=P(n)\setminus \{p_i\},i=1,\dots ,s\}.$ Then $C\cap B=\varphi$ as the elements of C are from the elements of one element ideal classes which are at level $(r-1)$ whereas the elements of B are from many element ideal classes. First we show that B is a proper subset of R. If possible, let R = B. Then two ideal $I,J\in S$ with level sets $L(I)=\left\{p_i\right\},L(J)=\left\{p_j\right\}$ are not resolved by any ideal $K\in B$ as $d(I,K)=d(J,K)=1$ where $K\in B\cap ({\cup }_{i=1}^{r-1}{A}_i)$ due to Corollary 2.1. This contradicts that R is a resolving set. Therefore, B is a proper subset of R and we may write $R=B\cup A$ where $A\subset V(G({\mathbb{Z}}_n))\setminus B$ with $1\le \left|A\right|\le s-1.$ Then the following possible cases arise.

Case-1: $A\subset {\cup }_{i=0}^{r-2}{A}_i.$ If $|A\cap S|=s-1,$ then there is an ideal $I\in S\setminus A.$ Let $L(I)=\left\{p_i\right\}$ for some $i\in \{1,2,\dots ,s\}.$ Then $d(I,K)=d(J,K)=1$ for all $K\in A,$ where $J\in V(G({\mathbb{Z}}_n))\setminus B$ with $L(J)=\varphi .$ This contradicts that $R=B\cup A$ is a resolving set. Again if $|A\cap S|<s-1,$ then there is at least two ideals $I,J\in S$ which are not in A. Let $L(I)=\left\{p_i\right\}$ and $L(I)=\left\{p_j\right\}$ for some $i,j\in \{1,2,\dots ,s\}$ with $i\ne j.$ Then by Corollary 2.1, $d(I,K)=d(J,K)=1$ for all $K\in A.$ Also we have shown that the elements of S are not resolved by B. Therefore we arrive at a contradiction that $R=B\cup A$ is not a resolving set.

Case-2: $A\subset A_{r-1}.$ If $|A\cap C|=s-1,$ then there is an ideal $I\in C\setminus A.$ Let $L(I)=P(n)\setminus \left\{p_i\right\}$ for some $i\in \{1,2,\dots ,s\}.$ Then for two ideals $I_1,I_2\in B$ having level sets distinct from $\left\{p_i\right\},d(I_1,K)=d(I_2,K)=1$ for all $K\in A.$This contradicts that $R=B\cup A$ is a resolving set. If $|A\cap C|<s-1,$ there is at least two ideals $I,J\in C\setminus A.$ Let $L(I)=P(n)\setminus \left\{p_i\right\}$ and $L(I)=P(n)\setminus \left\{p_i\right\},$ where $i,j\in \{1,2,\dots ,s\}.$ Then for two ideals $I_1,I_2\in B$ having level sets distinct from $\left\{p_i\right\}$ and $\left\{p_j\right\},d(I_1,K)=d(I_2,K)=1$ for all $K\in A$ due to Corollary 2.1. This contradicts that $R=B\cup A$ is a resolving set.

On account of all of the above cases we have $\beta (G({\mathbb{Z}}_n)\ge 2^s({\alpha }_{s+1}+1)({\alpha }_{s+2}+1)\dots ({\alpha }_r+1)+s-2^r-1.$ □

Theorem 3.2 gives a lower bound of the metric dimension for $G({\mathbb{Z}}_{p_1{p}_2\dots p_s{p}_{s+1}^{{\alpha }_{s+1}}\dots p_r^{{\alpha }_r}}).$ In the next theorem, we give $\beta (G({\mathbb{Z}}_{p_1{p}_2\dots p_s{p}_{s+1}^{{\alpha }_{s+1}}\dots p_r^{{\alpha }_r}})).$

Theorem 4.2.

For $n=p_1{p}_2\dots p_s{p}_{s+1}^{{\alpha }_{s+1}}\dots p_r^{{\alpha }_r}$, the metric dimension of $G({\mathbb{Z}}_n)$ is given by $$\beta (G({\mathbb{Z}}_n))=2^s({\alpha }_{s+1}+1)({\alpha }_{s+2}+1)\dots ({\alpha }_r+1)+s-2^r-1.$$

Proof.

From Theorem 3.2, $\beta (G({\mathbb{Z}}_n))\ge 2^s({\alpha }_{s+1}+1)({\alpha }_{s+2}+1)\dots ({\alpha }_r+1)+s-2^r-1.$ For the reverse inequality, let $B\subset V(G({\mathbb{Z}}_n)$ be the collection of ideals exactly one from each equivalence class of ρ as defined in Definition 2.3. Also let $C=\{I:L(I)=P(n)\setminus \{p_i\},i=1,\dots ,s\}.$ We show that $(V(G({\mathbb{Z}}_n))\setminus B)\cup C$ forms a resolving set for $G({\mathbb{Z}}_n).$ To prove this it is sufficient to show that elements of the set $B\setminus C$ have distinct codes. Let $I,J\in B\setminus C$ with level sets L(I) and L(J), respectively. Without loss of generality, we may assume $|L(J)|\le |L(I)|.$ Since I and J are distinct, there exists at least one $p_i\in P(n)$ such that $p_i\in L(I)$ but $p_i\notin L(J).$ Let K be an ideal with $L(K)=P(n)\setminus p_i.$ Then $|L(K)|=r-1$ and $K\in (V(G({\mathbb{Z}}_n))\setminus B)\cup C.$ Now by Corollary 2.1, $d(K,I)=1$ and by Theorem 2.1, $d(K,J)=2.$ Thus K resolves I and J and hence $(V(G({\mathbb{Z}}_n))\setminus B)\cup C$ forms a resolving set. Clearly, the cardinality of $(V(G({\mathbb{Z}}_n))\setminus B)\cup C$ is $2^s({\alpha }_{s+1}+1)({\alpha }_{s+2}+1)\dots ({\alpha }_r+1)+s-2^r-1$ and hence the theorem. □

Example 4.2.

For the graph $G({\mathbb{Z}}_{p_1{p}_2{p}_3^2}),[<p_1>]=\{<p_1>,<p_1{p}_3>\},[<p_2>]=\{<p_2>,<p_2{p}_3>\},[<p_1{p}_2>]=\{<p_1{p}_2>,<p_1{p}_2{p}_3>\}$ are many element ideal classes. $\beta (G({\mathbb{Z}}_{p_1{p}_2{p}_3^2}))=3+2=5.$ $\mathcal{B}=\{<p_1>,<p_2>,<p_1{p}_2>,<p_1{p}_3^2>,<p_2{p}_3^2>\}$ forms a minimal resolving set as the code of the remaining elements with respect to $\mathcal{B}$ are $(1,1,1,1,2),(1,1,1,2,1),(1,1,2,1,1),(1,1,1,1,1),(1,1,1,2,2),$ respectively.

5. Metric dimension of $G({\mathbb{Z}}_{p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_r^{{\alpha }_r}})$ where ${\alpha }_i\ge 2$

In this section we discuss the metric dimension of $G({\mathbb{Z}}_{p_1^{{\alpha }_1},p_2^{{\alpha }_2},p_3^{{\alpha }_3},\dots ,p_r^{{\alpha }_r}})$ with condition that all α_i’s are greater or equal to 2. Here vertex set is partitioned into $2^r-1$ ideal classes and all of these ideal classes are many element ideal classes. These ideal classes are also form twin sets. The following theorem gives the metric dimension of $G({\mathbb{Z}}_{p_1^{{\alpha }_1},p_2^{{\alpha }_2},\dots ,p_r^{{\alpha }_r}}),$ where ${\alpha }_i\ge 2.$

Theorem 5.1.

For $n=p_1^{{\alpha }_1},p_2^{{\alpha }_2},p_3^{{\alpha }_3},\dots ,p_r^{{\alpha }_r},\beta (G({\mathbb{Z}}_n))={\prod }_{i=1}^r({\alpha }_i+1)-2^r-1,$ where all α_i’s are greater or equal to 2.

Proof.

Let R be an arbitrary minimal resolving set for $G({\mathbb{Z}}_n).$ In $G({\mathbb{Z}}_n),2^r-1$ ideal classes (all ideal classes ) are many element ideal classes and each of these ideal classes forms a twin set. Let $T_1,\dots ,T_{2^r-1}$ be these twin sets. Applying Lemma 2.2, we have $|R\cap T_i|\ge \left|T_i\right|-1.$ Therefore $\left|R\right|\ge \sum (|T_i|-1)=|V(G({\mathbb{Z}}_n))|-(2^r-1)={\prod }_{i=1}^r({\alpha }_i+1)-2-(2^r-1)={\prod }_{i=1}^r({\alpha }_i+1)-2^r-1$ and hence $\beta (G({\mathbb{Z}}_n))\ge {\prod }_{i=1}^r({\alpha }_i+1)-2^r-1.$ For the reverse inequality, let B be a subset of ${\cup }_{i=1}^{2^r-1}{T}_i$ such that $|B\cap T_i|=\left|T_i\right|-1$ for each $i\in \{1,2,\dots ,2^r-1\}.$ We show that B forms a resolving set for $G({\mathbb{Z}}_n).$ Let $I,J\in V(G({\mathbb{Z}}_n))\setminus B.$ With out loss of generality, we may assume $|L(J)|\le |L(J)|.$ Since I and J are distinct, there exists at least one $p_i\in P(n)$ such that $p_i\in L(I)$ but $p_i\notin L(J).$ Again $d(K,I)=1$ and $d(K,J)=2$ for all $K\in B$ with $L(K)=P(n)\setminus p_i.$ Thus K resolves I and J. Therefore B forms a resolving set with cardinality ${\prod }_{i=1}^r({\alpha }_i+1)-2^r-1$ and hence the theorem. □

Example 5.1.

The graph $G({\mathbb{Z}}_{p_1^2{p}_2^2{p}_3^2})$ has metric dimension 18. For this graph $R=\{<p_1>,<p_3>,<p_2>,<p_1{p}_2>,<p_1{p}_3>,<p_2{p}_3>,<p_1^2>,<p_1^2{p}_2>,<p_1^2{p}_3>,<p_2^2>,<p_2^2{p}_1>,<p_2^2{p}_3>,<p_3^2>,<p_3^2{p}_2>,<p_3^2{p}_1>,<p_1^2{p}_2^2>,<p_1^2{p}_3^2>,<p_2^2{p}_3^2>\}$ is a resolving set with cardinality 18.

6. Conclusion

Every simple connected graph is isomorphic to some intersection graph. For the last few decades several mathematician studied intersection graphs on various algebraic structures and so it is naturally more convenient to study the intersection graph G(F) when the members of F have some algebraic structure. In this article, we consider the intersection graphs G(F) when the set F is an ideal and we determine the metric dimension of ideal intersection graphs $G({\mathbb{Z}}_n).$ Using similar type of arguments as we have used in this article, the researchers may find the metric dimension of ideal intersection graphs G(R) for any ring R which are isomorphic to some sub-ring of $({\mathbb{Z}}_n).$

Acknowledgments

We would like to thank heartily to our esteemed reviewers for reviewing this paper very consciously. Their valuable and precious comments were of immense help to make the paper more presentable and worthwhile. The first author is thankful to the Science and Research Board (SERB), DST, India for its financial support (Grant No. CRG/2019/006909).

Disclosure statement

No potential conflict of interest was reported by the author(s).