Upper dimension and bases of zero-divisor graphs of commutative rings

Abstract

For a commutative ring $R$ with non-zero zero divisor set $Z^{\ast }\left(R\right)$, the zero divisor graph of $R$ is $\Gamma \left(R\right)$ with vertex set $Z^{\ast }\left(R\right)$, where two distinct vertices $x$ and $y$ are adjacent if and only if $xy=0$. The upper dimension and the resolving number of a zero divisor graph $\Gamma \left(R\right)$ of some rings are determined. We provide certain classes of rings which have the same upper dimension and metric dimension and give an example of a ring for which these values do not coincide. Further, we obtain some bounds for the upper dimension in zero divisor graphs of commutative rings and provide a subset of vertices which cannot be excluded from any resolving set.

Keywords:

• Ring
• Zero-divisor graph
• Upper dimension
• Resolving number

1 Introduction

Throughout this article, we will consider only commutative rings $R$ with unity $1\ne 0$, and we will let $Z\left(R\right)$ be the set of zero divisors of $R$. The zero divisor graph of $R$ denoted by $\Gamma \left(R\right)$ is the undirected graph having vertex set $V\left(\Gamma \left(R\right)\right)=Z^{\ast }\left(R\right)=Z\left(R\right)\setminus \left\{0\right\}$, with distinct vertices $x$ and $y$ being adjacent if and only if $xy=0$. This definition of the zero divisor graph is due to D.F. Anderson and Livingston [1], who extended the earlier work of Beck [2] and D.D. Anderson and Naseer [3] which used all zero-divisors of the ring as vertices. The zero divisor graph translates the algebraic properties of a ring to graph theoretical tools, and therefore it can help in exploring interesting results in both graph theory and abstract algebra. The zero-divisor graph of a commutative ring has been studied by many authors and has been extended to several other algebraic structures.

This paper is organized as follows. In Section 2, we analyze the relation between the upper dimension and the graph structure of $\Gamma \left(R\right)$ for a commutative ring $R$. Rings with finite metric dimension and those for which upper dimension and resolving number are same are characterized. In Section 3, it is shown that the upper dimension and metric dimension (lower dimension) are the same in zero divisor graphs for all finite commutative rings of odd characteristic and for rings of order $2k$, where $k$ is an odd integer. Finally, several examples are discussed, with methods to compute the upper dimension.

2 Upper dimension and bases of $\Gamma \left(R\right)$

The concept of metric dimension of a graph was introduced in 1970s by Slater [4] and independently by Harary and Melter [5]. The concept of $upperdimension$ of graphs was introduced by Chartrand et al. [6].

Definition 2.1

Consider a connected graph $G$ on $n$ vertices. For a given vertex $v\in V\left(G\right)$, the representation $r(v\mid W)$ for $v$ with respect to an ordered set $W=\{w_1,w_2,\dots ,w_k\}$ of vertices of $G$ is a $k$-tuple defined as $$r(v\mid W)=(d(v,w_1),d(v,w_2),\dots ,d(v,w_k)),$$where $d(x,y)$ represents the distance between the two vertices $x$ and $y$ of $G$. Clearly, the representation for the $i$th vertex in $W$ has 0 in the $i$th coordinate and all other coordinates are non-zero. So the vertices of $W$ necessarily have distinct representations. Thus the representations of only those vertices that are not in $W$ need to be examined to check if these representations are distinct. The set $W$ is called a $resolvingset$ if all vertices of $G$ have different representations with respect to $W$. A resolving set $W$ is called a $minimalresolvingset$ if no proper subset of $W$ is a resolving set of $G$. A minimal resolving set containing the minimum number of vertices is called a $metricbasis$ for $G$ and the cardinality of a metric basis is called the $metricdimension$ of $G$, denoted by $dim\left(G\right)$. A minimal resolving set with the largest number of vertices is called an $upperbasis$ of $G$ and its cardinality is called the $upperdimension$ which is denoted by $di{m}^{+}\left(G\right)$. It is obvious that for a graph on $n$ vertices, every subset of $(n-1)$ vertices is a resolving set. Thus, for any connected graph $G,di{m}^{+}\left(G\right)\le n-1$.

The $resolvingnumber$, denoted by $res\left(G\right)$, of a connected graph $G$ is the smallest positive integer $k$ such that every set of $k$ vertices of $G$ is a resolving set of $G$. Since the order of an upper basis is the largest minimal resolving set and resolving number is the order of a resolving set (whether minimal or not) we have the following inequality on metric dimension, upper dimension and the resolving number for a connected graph $G$ of order $n\ge 2$, $$1\le dim\left(G\right)\le di{m}^{+}\left(G\right)\le res\left(G\right)\le n-1$$

We begin by summarizing some results on metric dimension and upper dimension of graphs which will be used in throughout this section. For undefined notations and terminology from graph theory, the readers are refered to [7].

Lemma 2.1

Lemma 2.2 [8] For a connected graph $G$ of order $n\ge 1$,$di{m}^{+}\left(G\right)=1$ if and only if $G\cong P_2$ or $P_3$ and, for $n\ge 4$,$di{m}^{+}\left(P_n\right)=2$, where$P_n$ denotes the path on $n$ vertices.

Lemma 2.2

Lemma 2.4 [8] A connected graph $G$ of order $n$ has upper dimension equal to $n-1$ if and only if $G\cong K_n$.

Lemma 2.3

Lemma 2.5 [8] The upper dimension of a cycle $C_n$ is 2, where $n\ge 3$ is a positive integer.

Theorem 2.4

Theorem 4.2 [8] For a positive integer $n\ge 3$,$di{m}^{+}(K_{1,n}\times K_2)=di{m}^{+}\left(K_{1,n}\right)+1=n$.

In this and later sections, we denote the ring of integers by $\mathbb{Z}$, the ring of integers modulo $n$ by ${\mathbb{Z}}_n$, and the field with $q$ elements by ${\mathbb{F}}_q$. As we now begin to discuss zero-divisor graphs of commutative rings, we remind the reader of the most fundamental characteristics of the structure of such graphs.

Theorem 2.5

Theorem 2.3 [1] Let $R$ be a commutative ring. Then $\Gamma \left(R\right)$ is connected and $diam\left(\Gamma \left(R\right)\right)\le 3$.

Lemma 2.6

If $R$ is a commutative ring with unity such that $\Gamma \left(R\right)$ is a path, then $\left|Z^{\ast }\left(R\right)\right|\le 3$.

Proof

By [Theorem 2.3 [1]], $\Gamma \left(R\right)$ is connected and $diam\left(\Gamma \left(R\right)\right)\le 3$. Thus, $\Gamma \left(R\right)$ cannot be a path of length greater than 4.

If possible, let $\left|Z^{\ast }\left(R\right)\right|=4$ for some ring $R$, where $\Gamma \left(R\right)$ is a path, say $a-b-c-d$ such that $ab=bc=cd=0$ are the only zero divisor relations. Note that $a+c\in Z\left(R\right)$ since $b(a+c)=0$. Clearly, $a+c\ne a$ and $a+c\ne c$. Also, $a+c\ne d$ since $bd\ne 0$ and $a+c\ne 0$ since $d(a+c)=da+dc=da\ne 0$. Therefore, $a+c=b$. A similar argument shows $c=b+d$. Hence, $c-d=b=a+c$. Thus $a=-d$. However, this is a contradiction, since $-dc=0$ but $ac\ne 0$. Thus, $\left|Z^{\ast }\left(R\right)\right|=4$ is not possible.□

Theorem 2.7

Let $R$ be a commutative ring with unity. Then $di{m}^{+}\left(\Gamma \left(R\right)\right)=1$ if and only if $R$ is one of the following rings.

(i)	$\frac{{\mathbb{Z}}_3\left[x\right]}{\left(x^2\right)}$, ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$, ${\mathbb{Z}}_9$.
(ii)	${\mathbb{Z}}_6$, ${\mathbb{Z}}_8$, $\frac{{\mathbb{Z}}_2\left[x\right]}{\left(x^3\right)}$, $\frac{{\mathbb{Z}}_4\left[x\right]}{(2x,x^2-2)}$.

Proof

The lists here give the only rings (up to isomorphism) whose zero-divisor graph is isomorphic to (i) $P_2$ or (ii) $P_3$. Hence, the result follows by Lemmas 2.6 and 2.1. □

Notice that $di{m}^{+}\left(\Gamma \left(R\right)\right)=1$ if and only if $\Gamma \left(R\right)$ is a path by Lemma 2.1. However, the same is not true for a graph $G$ in general, since $di{m}^{+}\left(G\right)\ge 2$ if $G\ne P_2,P_3$. Further, if $\Gamma \left(R\right)$ is a path, then $\Gamma \left(R\right)$ has exactly two upper basis sets, since only the end vertex forms a resolving set.

Theorem 2.8

Let $R$ be a commutative ring with unity. Then $di{m}^{+}\left(\Gamma \left(R\right)\right)$ is finite if and only if $R$ is finite (and not a domain).

Proof

If $R$ is finite, then $\left|Z^{\ast }\left(R\right)\right|$ is finite and therefore $di{m}^{+}\left(\Gamma \left(R\right)\right)$ is finite. Now, suppose $di{m}^{+}\left(\Gamma \left(R\right)\right)$ is finite. Let $W$ be the upper basis set with $\left|W\right|=k$, where $k$ is some positive integer. For any two vertices $x$ and $y$ of $\Gamma \left(R\right)$, $d(x,y)\in \{0,1,2,3\}$ by Theorem 2.5. Now, for each vertex $x\in Z^{\ast }\left(R\right)$, the representation $r(x\mid W)$ is a $k-$ coordinate vector $(d_1,d_2,\dots ,d_k)$, where each $d_i\in \{0,1,2,3\},1\le i\le k$. As each $d_i$ has four possibilities, therefore the total number of possibilities for $r(x\mid W)$ is $4^k$. Since $W$ is a resolving set, therefore $r(x\mid W)$ is unique for each vertex $x\in Z^{\ast }\left(R\right)$ so that $\left|Z^{\ast }\left(R\right)\right|\le 4^k$. This implies that $Z^{\ast }\left(R\right)$ is finite and hence $R$ is finite.□

Note that $di{m}^{+}\left(\Gamma \left(R\right)\right)$ is finite if and only if $R$ is finite, let $di{m}^{+}\left(\Gamma \left(R\right)\right)=k$ and let $W=\{w_1,w_2,\dots ,w_k\}$ be the upper basis. Since each coordinate of $r\left(x\right|W)$ is non-zero whenever $x\in V\left(\Gamma \left(R\right)\right)-W$, we see that every coordinate in $r\left(x\right|W)$ belongs to the set $\{1,2,3\}$, as $diam\left(\Gamma \left(R\right)\right)\le 3$. Therefore $\left|Z^{\ast }\left(R\right)\right|\le 3^k+k$. We note that this is a better bound than given in proof of Theorem 2.8 as $3^k+k<4^k$ for all $k\ge 2$.

Corollary 2.9

Let $R$ be a commutative ring with unity 1 (and not a domain) such that$di{m}^{+}\left(\Gamma \left(R\right)\right)=k$, where$k$ is any positive integer. Then $\left|Z\left(R\right)\right|\le 4^k+1$.

If $R$ is a commutative ring (and not a domain), we also notice that $\left|Z\left(R\right)\right|\le 4^k+1$ gives $k\ge \lceil lo{g}_4(\left|Z\left(R\right)\right|-1)\rceil =\lceil log\left(\left|Z^{\ast }\left(R\right)\right|\right)\rceil$, thus we have a lower bound for the upper dimension of $\Gamma \left(R\right)$. The equality holds when $\left|\Gamma \left(R\right)\right|=\text{1,2}$. For a ring $R$, $di{m}^{+}\left(\Gamma \left(R\right)\right)=res\left(\Gamma \left(R\right)\right)=1$ if and only if $\Gamma \left(R\right)\cong P_2$, that is, if and only if $R\cong \frac{{\mathbb{Z}}_3\left[x\right]}{\left(x^2\right)}$, ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$, ${\mathbb{Z}}_9$.

Theorem 2.10

Let $R$ be a commutative ring with unity.

(i)	$di{m}^{+}\left(\Gamma \left(R\right)\right)=res\left(\Gamma \left(R\right)\right)=2$ if and only if $R\cong$ $\frac{{\mathbb{F}}_4\left[x\right]}{\left(x^2\right)}$, $\frac{{\mathbb{Z}}_4\left[x\right]}{(x^2+x+1)}$, $\frac{{\mathbb{Z}}_4\left[x\right]}{{(2,x)}^2}$, $\frac{{\mathbb{Z}}_2[x,y]}{{(x,y)}^2}$.
(ii)	$di{m}^{+}\left(\Gamma \left(R\right)\right)=res\left(\Gamma \left(R\right)\right)=\left|Z^{\ast }\left(R\right)\right|-1$ if and only if $\Gamma \left(R\right)$ is complete

Proof

(i) To prove the result, we show if $di{m}^{+}\left(\Gamma \left(R\right)\right)=res\left(\Gamma \left(R\right)\right)=2$, then $\Gamma \left(R\right)$ is either a path or a cycle. For this, we first show that $\Delta \left(\Gamma \left(R\right)\right)=2$, where $\Delta \left(\Gamma \left(R\right)\right)=2$ denotes the largest degree of a vertex in $\Gamma \left(R\right)$.

We claim that there does not exist a subset of vertices $D=\{x,a,b,c\}$ in $\Gamma \left(R\right)$ with the property $ax=bx=cx=0$ and the restriction $res\left(\Gamma \left(R\right)\right)=2$, for otherwise, we have the following cases as given in Fig. 1. In each of the four graphs in Fig. 1, the bold vertices represent the set of two vertices that do not form a resolving set. Thus, the graphs $\left(a\right),\left(b\right),\left(c\right),\left(d\right)$ in Fig. 1 completely describe the situation that a graph having a vertex of degree 3 or more cannot have resolving number equal to 2. Therefore, we must have $\Delta \left(\Gamma \left(R\right)\right)\le 2$. Also, if $\Delta \left(\Gamma \left(R\right)\right)=1$, then $\Gamma \left(R\right)=P_2$ and $res\left(P_2\right)=1$. Thus, we have $\Delta \left(\Gamma \left(R\right)\right)=2$. Hence $\Gamma \left(R\right)$ is either a path $P_3$ or a cycle $C_3$ or $C_4$. Therefore, we must have $\Gamma \left(R\right)\cong C_3$ or $C_4$. Since the two non-adjacent vertices of $C_4$ do not form a resolving set, therefore $\Gamma \left(R\right)\cong C_3$ and so $R\cong$ $\frac{{\mathbb{F}}_4\left[x\right]}{\left(x^2\right)}$, $\frac{{\mathbb{Z}}_4\left[x\right]}{(x^2+x+1)}$, $\frac{{\mathbb{Z}}_4\left[x\right]}{{(2,x)}^2}$, $\frac{{\mathbb{Z}}_2[x,y]}{{(x,y)}^2}$.

(ii). Clearly $di{m}^{+}\left(\Gamma \left(R\right)\right)\le res\left(\Gamma \left(R\right)\right)\le n-1$ and any subset of $n-1$ vertices of complete graph forms a resolving set. Hence, the result follows by Lemma 2.2. □

short-legendFig. 1

Example 2.11

It is easily verified that if $R\cong$ ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$, ${\mathbb{Z}}_2\times \frac{{\mathbb{Z}}_2\left[x\right]}{\left(x^2\right)}$, ${\mathbb{Z}}_2\times {\mathbb{F}}_4$, ${\mathbb{Z}}_2\times {\mathbb{Z}}_2\times {\mathbb{Z}}_2$, ${\mathbb{Z}}_3\times {\mathbb{Z}}_3$, then $di{m}^{+}\left(\Gamma \left(R\right)\right)=2$. However, in each case, one can find a set of two distinct vertices of $\Gamma \left(R\right)$ that do not form a resolving set. Thus $res\left(\Gamma \left(R\right)\right)>2$.

Recall that an element $x$ in a ring $R$ is said to be nilpotent if there exists a positive integer $k$ such that $x^k=0$.

Theorem 2.12

Let $R$ be a ring where every zero-divisor is nilpotent.

(i)	If $\left|Z^{\ast }\left(R\right)\right|=1$ or 2, then $di{m}^{+}\left(\Gamma \left(R\right)\right)=1$.
(ii)	If $\left|Z^{\ast }\left(R\right)\right|\ge 3$, and $Z{\left(R\right)}^2=\left\{0\right\}$, then $di{m}^{+}\left(\Gamma \left(R\right)\right)=\left|Z^{\ast }\left(R\right)\right|-1$.
(iii)	If $\left|Z^{\ast }\left(R\right)\right|\ge 3$, and $Z{\left(R\right)}^2\ne \left\{0\right\}$, then $di{m}^{+}\left(\Gamma \left(R\right)\right)\le \left|Z^{\ast }\left(R\right)\right|-2$.

Proof

(i) If $\left|Z^{\ast }\left(R\right)\right|=1$, then $R\cong {\mathbb{Z}}_4$ or $\frac{{\mathbb{Z}}_2}{\left(x^2\right)}$ and so $\Gamma \left(R\right)=K_1$. If $\left|Z^{\ast }\left(R\right)\right|=2$, then $R\cong {\mathbb{Z}}_9$ or ${\mathbb{Z}}_3\left[x\right]∕\left(x^2\right)$ or ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$ and so $\Gamma \left(R\right)=K_2$. Therefore, in each case $di{m}^{+}\left(\Gamma \left(R\right)\right)=1$.

(ii) If $\left|Z^{\ast }\left(R\right)\right|\ge 3$, and $Z{\left(R\right)}^2=\left\{0\right\}$, then $xy=0$ for all $x,y\in Z^{\ast }\left(R\right)$, by Theorem 2.8 [1]. Thus, $\Gamma \left(R\right)$ is a complete graph and so by Lemma 2.2, $di{m}^{+}\left(\Gamma \left(R\right)\right)=\left|Z^{\ast }\left(R\right)\right|-1$.

(iii) If $\left|Z^{\ast }\left(R\right)\right|\ge 3$ and $Z{\left(R\right)}^2\ne \left\{0\right\}$, there exists some $x\in Z^{\ast }\left(R\right)$ such that $x^2\ne 0$. So there exists $y\in Z^{\ast }\left(R\right)$ such that $d(x,y)\ge 2$. Therefore, $di{m}^{+}\left(\Gamma \left(R\right)\right)\le \left|Z^{\ast }\left(R\right)\right|-2$ as $Z^{\ast }\left(R\right)-\{z,y\}$ is a resolving set for any vertex $z$ adjacent to $x$. □

3 Characteristic of a Ring and Star Subsets

Resolving sets for zero-divisor graphs have previously been studied in [9] and [10]. In these articles, it was noted that distance similarity was a key factor in determining resolving sets. Vertices $x$ and $y$ of a graph $G$ are called $distancesimilar$ if $d(x,a)=d(y,a)$ for all $a\in V\left(G\right)-\{x,y\}$. The following results illustrate this connection between concepts.

Theorem 3.1

Theorem 2.1 [9] Let $G$ be a connected graph. Suppose $G$ is partitioned into $k$ distinct distance similar classes $V_1,V_2,\dots ,V_k$ (that is, $x,y\in V_i$ if and only if $d(x,a)=d(y,a)$ for all $a\in V\left(G\right)-\{x,y\}$).

(i)	Any resolving set $W$ for $G$ contains all but at most one vertex from each $V_i$.
(ii)	Each $V_i$ induces a complete subgraph or a graph with no edges.
(iii)	$dim\left(G\right)\ge \left|V\left(G\right)\right|-k$.
(iv)	There exists a minimal resolving set $W$ for $G$ such that if $\left|V_i\right|>1$, at most $\left|V_i\right|-1$ vertices of $v_i$ are elements of $W$.
(v)	If $m$ is the number of distance similar classes that consist of a single vertex, then $\left|V\left(G\right)\right|-k\le dim\left(G\right)\le \left|V\left(G\right)\right|-k+m$.

The characteristic of a ring $R$ is the least positive integer $n$ such that $nx=0$ for all $x\in R$, where 0 is the zero element of $R$. If no such integer exists, we say that $R$ has characteristic 0.

Theorem 3.2

Let $R$ be a finite commutative ring that is not a field such that $R$ has odd characteristic. Then $di{m}^{+}\left(\Gamma \left(R\right)\right)=dim\left(\Gamma \left(R\right)\right)$.

Proof

Since the characteristic of $R$ is odd, $x$ and $-x$ are distance similar for any vertex $x$ and $x\ne -x$. Thus, by Theorem 3.1, $di{m}^{+}\left(\Gamma \left(R\right)\right)=dim\left(\Gamma \left(R\right)\right)$. □

Theorem 3.3

Let $S$ be a finite commutative ring of order 2$k$, where $k$ is an odd integer. Then $di{m}^{+}\left(\Gamma \left(S\right)\right)=dim\left(\Gamma \left(S\right)\right)$.

Proof

It can be shown that $S\simeq {\mathbb{Z}}_2\times R$ for some finite ring $R$ with odd characteristic. If $R$ is a domain, then $\Gamma \left(S\right)$ is a star-graph and the result follows from Theorem 2.4. (It is also trivial to prove that $di{m}^{+}\left(\Gamma ({\mathbb{Z}}_2\times {\mathbb{Z}}_p)\right)=dim\left(\Gamma ({\mathbb{Z}}_2\times {\mathbb{Z}}_p)\right)$, where p is prime). Hence, we assume that $R$ is not a domain for the rest of the proof.

The elements of $v\left(\Gamma \left(S\right)\right)$ can be partitioned into the sets $A=\left\{(0,x)\right|x\in Z{\left(R\right)}^{\ast }\}$, $B=\left\{(0,y)\right|y\in R-Z\left(R\right)\}$, $C=\left\{(1,x)\right|x\in Z{\left(R\right)}^{\ast }\}$ and $D=\left\{(1,0)\right\}$. Note that $\left|B\right|>1$ since $R-Z\left(R\right)\ne 0̸$ and $z\in R-Z\left(R\right)$ implies $-z\in R-Z\left(R\right)$ with $z\ne -z$. Also, all elements of $B$ are distance similar as any element of $B$ is only adjacent to (1, 0). If $x$ and $y$ are distance similar vertices of $\Gamma \left(R\right)$, then both $(0,x)$ and $(0,y)$ are distance similar in $\Gamma \left(S\right)$ and $(1,x)$ and $(1,y)$ are distance similar in $\Gamma \left(S\right)$. (For example, $d((a,b),(0,x))=1$ if and only if $(a,b)(0,x)=(0,0)$ if and only if $bx=0$ if and only if $by=0$ if and only if $(a,b)(0,y)=(0,0)$ if and only if $d((a,b),(0,y))=1$). Thus, when $v\left(\Gamma \left(S\right)\right)$ is partitioned into distance similar classes (as in Theorem 3.1), the only class that will have one element is $D=\left\{(1,0)\right\}$.

Next, we show (1, 0) cannot be an element of any minimal resolving set for $\Gamma \left(S\right)$. Suppose $W$ is a resolving set with $(1,0)\in W$. Let $W^{\ast }=W-\left\{(1,0)\right\}$. We show that $W^{\ast }$ is also a resolving set. Note that $W^{\ast }\cap B\ne 0̸$. So, let $c\in W^{\ast }\cap B$. Then, for all $s\in v\left(\Gamma \left(S\right)\right)-W^{\ast }$, $r(s,W^{\ast })\ne r((1,0),W^{\ast })$ because (1,0) is the only vertex of $\Gamma \left(S\right)$ whose distance to $c$ is 1. So, suppose $x,y\in v\left(\Gamma \left(S\right)\right)-W$ with $x\ne y$ but $r(x,W^{\ast })=r(y,W^{\ast })$. However, since $W$ is a resolving set, this implies $d((1,0),x)\ne d((1,0),y)$ and $d(z,x)=d(z,y)$ for all $z\in W^{\ast }$. This is impossible if both $x$ and $y$ are in $A\cup B$, since all elements of $A\cup B$ are distance 1 from (1, 0). If $x,y\in C$, then $x=(1,x_2)$ and $y=(1,y_2)$, for some $x_2,y_2\in Z{\left(R\right)}^{\ast }$. Clearly, $d(x,(1,0))>1$ and $d(y,(1,0))>1$. There must exist some $x_3,y_3\in Z{\left(R\right)}^{\ast }$ such that $x_2{x}_3=0$ and $y_2{y}_3=0$. However, this implies $d(x,(1,0))=d(y,(1,0))=2$ via the paths $x-(0,x_3)-(1,0)$ and $y-(0,y_3)-(1,0)$. Hence, it must be the case that (without loss of generality) $x\in A\cup B$ and $y\in C$. Thus $y=(1,y_2)$ for some $y_2\in Z{\left(R\right)}^{\ast }$. Suppose $x\in A$ with $x=(0,x_2)$ for some $x_2\in Z{\left(R\right)}^{\ast }$. Then there is some $t\in Z{\left(R\right)}^{\ast }$ with $x_{2}t=0$. Therefore, there must be some $t^{\ast }\in Z{\left(R\right)}^{\ast }$ such that $t$ and $t^{\ast }$ are distance similar with $(1,t^{\ast })\in W^{\ast }$. However, this implies $d(x,(1,t^{\ast }))=1$ but $d(y,(1,t^{\ast }))\ne 1$. If $x\in B$ with $x=(0,u)$ for some $u\in Z{\left(R\right)}^{\ast }$, then there is some $v\in Z{\left(R\right)}^{\ast }$ with $v{y}_2=0$. Therefore, there must be some $v^{\ast }\in Z{\left(R\right)}^{\ast }$ such that $v$ and $v^{\ast }$ are distance similar and $(0,v^{\ast })\in W^{\ast }$. Then $d(y,(0,v^{\ast }))=1$ and $d(x,(0,v^{\ast }))\ne 1$. Hence, in all cases, $r(x\left|W^{\ast }\right)\ne r\left(y\right|W^{\ast })$.

Finally, we show that every minimal resolving set of $\Gamma \left(S\right)$ must contain all but one element of each distance similar class. Let $K_1,K_2,\dots ,K_n$ be the partition of $\Gamma \left(S\right)$ into distance similar classes (as in Theorem 3.1). By Theorem 3.1, $|W\cap K_i|\ge \left|K_i\right|-1$ for any minimal resolving set $W$. Therefore, assume $|W\cap K_i|=\left|K_i\right|$ (that is, $K_i\subseteq W_1$) for some minimal resolving set $W_1$ and some $1\le i\le n$ with $K_i\ne \left\{(1,0)\right\}$.

Let $x_1\in K_i$ and let $W^{\ast }=W_1-\left\{x_1\right\}$. As in Theorem 3.1, we will show that $W_1$ is not a minimal resolving set by showing that $W^{\ast }$ is a resolving set. Let $a,b\in V\left(\Gamma \left(S\right)\right)-W_1$. Then $r(a\left|W_1\right)\ne r\left(b\right|W_1)$, implying there is some $c\in W_1$ with $d(a,c)\ne d(b,c)$. If $c\ne x_1$, then $c\in W^{\ast }$ and $r(a\left|W^{\ast }\right)\ne r\left(b\right|W^{\ast })$. If $c=x_1$, then let $v\in K_i$ with $v\ne x_1$. Therefore, $v$ and $x_1$ are distance similar and $d(a,v)=d(a,x_1)\ne d(b,x_1)=d(b,v)$. Hence, $r(a\left|W^{\ast }\right)\ne r\left(b\right|W^{\ast })$. Finally, if $t\in V\left(\Gamma \left(S\right)\right)-W^{\ast }$ with $t\ne x_1$, then $t$ is not distance similar to $x_1$. Thus, there is some vertex $z\in V\left(\Gamma \left(S\right)\right)-\{t,x_1\}$ such that $d(t,z)\ne d(x_1,z)$. If $z\ne (1,0)$, there is some $z^{\ast }\in W^{\ast }$ such that $z=z^{\ast }$ or $z$ is distance similar to $z^{\ast }$. Thus, $d(t,z^{\ast })=d(t,z)\ne d(x_1,z)=d(x_1,z^{\ast })$.

However, suppose $z=(1,0)$. Choose $u\in R-Z\left(R\right)$ such that $(0,u)\in W^{\ast }$. Then, since the only vertex adjacent to $(0,u)$ is (1, 0), we have $d((0,u),t)=d((0,u),(1,0))+d((1,0),t)=1+d((1,0),t)\ne 1+d((1,0),x_1)=d((0,u),(1,0))+d((1,0),x_1)=d((0,u),x_1)$. Therefore, $r(t\left|W^{\ast }\right)\ne r\left(x_1\right|W^{\ast })$. □

Definition 3.1

A vertex of degree one (that is, a vertex adjacent to only one other vertex) is called a $pendantvertex$. Call the vertices which are adjacent with at least one pendent vertex $star$ $vertices$ and the subset of all such vertices a $starsubset$. Also, the number of pendent edges incident on $v$ is called the $star$ $degree$ of $v$, denoted by $sdeg\left(v\right)$. Clearly, if $d\left(v\right)$ denotes the degree of a vertex $v$, then $sdeg\left(v\right)\le d\left(v\right)$ and the equality holds in star graphs. Also, a tree that is not a star graph has at least two star vertices.

Theorem 3.4

Let $G$ be a graph of order $n$ with vertex set $V\left(G\right)$ and a star subset $X=\{x_1,x_2,\dots ,x_p\}$ such that the star degree of $x_i$ is $k_i\ge 2$ for all $1\le i\le p$. Then $di{m}^{+}\left(G\right)\ge k-p$, where $k=k_1+k_2+\cdots +k_p$.

Proof

For $1\le i\le p$, choose $x_i$, and let $v_1,v_2,\dots ,v_{k_i},k_i>1$ be pendent vertices incident on $x_i$. Then $v_m$ is distance similar to $v_j$ for each $1\le m\le k_i$ and $1\le j\le k_i$. Therefore, by Theorem 3.1, a subset of at least $k_i-1$ of the vertices $\{v_1,v_2,\dots ,v_{k_i}\}$ must be contained in any minimal resolving set. Thus any resolving set has cardinality greater than or equal to $k_1+k_2+\cdots +k_p-p=k-p$. □

Corollary 3.5

Let $G$ be a graph as inTheorem 3.4. If, in addition, $G$ is the zero divisor graph of some commutative ring, then$k-p\le di{m}^{+}\left(G\right)\le n-p$, where$k=k_1+k_2+\cdots +k_p$.

Example 3.6

By using the results in this article and examining the graphs found in [11], one can determine the upper dimension of all zero divisor graphs of a commutative ring with up to 14 vertices. Out of these examples, there is only one ring $R$ such that $dim\left(\Gamma \left(R\right)\right)\ne di{m}^{+}\left(\Gamma \left(R\right)\right)$. For $R\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2\times {\mathbb{Z}}_2\times {\mathbb{Z}}_2$, $dim\left(\Gamma \left(R\right)\right)=3$ with $W=\{(1,1,1,0),(1,1,0,1),(1,0,1,1)\}$ an example of a minimal resolving set. However, it is straightforward to verify that $V=\{(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)\}$ also defines a resolving set for $\Gamma \left(R\right)$. We can see that $V$ is minimal, as removing (1,0,0,0) would give $r((1,1,1,0)\left|V\right)=r\left((0,1,1,0)\right|V)$, removing (0,1,0,0) will give $r((1,1,1,0)\left|V\right)=r\left((1,0,1,0)\right|V)$, removing (0,0,1,0) will give $r((1,1,1,0)\left|V\right)=r\left((1,1,0,0)\right|V)$, and removing (0,0,0,1) will give $r((1,1,0,1)\left|V\right)=r\left((1,1,0,0)\right|V)$.

It is also interesting to note that for most of the zero divisor graphs on 14 or fewer vertices, a minimal resolving set can be determined by looking at classes of distance similar vertices — in particular, if $K_1,K_2,\dots ,K_p$ is a partition of $v\left(\Gamma \left(R\right)\right)$ into distance similar sets of vertices, then a minimal resolving set is formed by taking all but one element from each $K_i$. The only exceptions are as follows.

(i)	for $R\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2$ or ${\mathbb{Z}}_9$ or ${\mathbb{Z}}_3\left[x\right]∕\left(x^2\right)$, (where $\Gamma \left(R\right)\cong K_2$ and vacuously no distinct vertices of $\Gamma \left(R\right)$ are distance similar).
(ii)	for $R\cong {\mathbb{Z}}_2\times \frac{{\mathbb{Z}}_2\left[x\right]}{\left(x^2\right)}$ or ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$, when $\Gamma \left(R\right)$ has only one pair of distance similar vertices but $dim\left(\Gamma \left(R\right)\right)=di{m}^{+}\left(\Gamma \left(R\right)\right)=2$.
(iii)	for $R\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2\times {\mathbb{Z}}_2$, when no two distinct vertices of $\Gamma \left(R\right)$ are distance similar.
(iv)	for $R\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2\times {\mathbb{Z}}_2\times {\mathbb{Z}}_2$, when no two distinct vertices of $\Gamma \left(R\right)$ are distance similar.

Acknowledgments

The authors are grateful to the anonymous referee for his useful suggestions which improved the presentation of the paper. This research is supported by JRF financial assistance (second author) by Council of Scientific and Industrial Research (CSIR), New Delhi India and the University Grants Commission, New Delhi with research project number MRP-MAJOR-MATH-2013-8034 (first author).