![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
For a commutative ring with non-zero zero divisor set
, the zero divisor graph of
is
with vertex set
, where two distinct vertices
and
are adjacent if and only if
. The upper dimension and the resolving number of a zero divisor graph
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.
1 Introduction
Throughout this article, we will consider only commutative rings with unity
, and we will let
be the set of zero divisors of
. The zero divisor graph of
denoted by
is the undirected graph having vertex set
, with distinct vertices
and
being adjacent if and only if
. This definition of the zero divisor graph is due to D.F. Anderson and Livingston Citation[1], who extended the earlier work of Beck Citation[2] and D.D. Anderson and Naseer Citation[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 for a commutative ring
. 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
, where
is an odd integer. Finally, several examples are discussed, with methods to compute the upper dimension.
2 Upper dimension and bases of ![](//:0)
![](//:0)
The concept of metric dimension of a graph was introduced in 1970s by Slater Citation[4] and independently by Harary and Melter Citation[5]. The concept of of graphs was introduced by Chartrand et al. Citation[6].
Definition 2.1
Consider a connected graph on
vertices. For a given vertex
, the representation
for
with respect to an ordered set
of vertices of
is a
-tuple defined as
where
represents the distance between the two vertices
and
of
. Clearly, the representation for the
th vertex in
has 0 in the
th coordinate and all other coordinates are non-zero. So the vertices of
necessarily have distinct representations. Thus the representations of only those vertices that are not in
need to be examined to check if these representations are distinct. The set
is called a
if all vertices of
have different representations with respect to
. A resolving set
is called a
if no proper subset of
is a resolving set of
. A minimal resolving set containing the minimum number of vertices is called a
for
and the cardinality of a metric basis is called the
of
, denoted by
. A minimal resolving set with the largest number of vertices is called an
of
and its cardinality is called the
which is denoted by
. It is obvious that for a graph on
vertices, every subset of
vertices is a resolving set. Thus, for any connected graph
.
The , denoted by
, of a connected graph
is the smallest positive integer
such that every set of
vertices of
is a resolving set of
. 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
of order
,
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 Citation[7].
Lemma 2.1
Lemma 2.2 Citation[8] For a connected graph of order
,
if and only if
or
and, for
,
, where
denotes the path on
vertices.
Lemma 2.2
Lemma 2.4 Citation[8] A connected graph of order
has upper dimension equal to
if and only if
.
Lemma 2.3
Lemma 2.5 Citation[8] The upper dimension of a cycle is 2, where
is a positive integer.
Theorem 2.4
Theorem 4.2 Citation[8] For a positive integer ,
.
In this and later sections, we denote the ring of integers by , the ring of integers modulo
by
, and the field with
elements by
. 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 Citation[1] Let be a commutative ring. Then
is connected and
.
Lemma 2.6
If is a commutative ring with unity such that
is a path, then
.
Proof
By [Theorem 2.3 Citation[1]], is connected and
. Thus,
cannot be a path of length greater than 4.
If possible, let for some ring
, where
is a path, say
such that
are the only zero divisor relations. Note that
since
. Clearly,
and
. Also,
since
and
since
. Therefore,
. A similar argument shows
. Hence,
. Thus
. However, this is a contradiction, since
but
. Thus,
is not possible.□
Theorem 2.7
Let be a commutative ring with unity. Then
if and only if
is one of the following rings.
(i) |
| ||||
(ii) |
|
Proof
The lists here give the only rings (up to isomorphism) whose zero-divisor graph is isomorphic to (i) or (ii)
. Hence, the result follows by Lemmas 2.6 and 2.1. □
Notice that if and only if
is a path by Lemma 2.1. However, the same is not true for a graph
in general, since
if
. Further, if
is a path, then
has exactly two upper basis sets, since only the end vertex forms a resolving set.
Theorem 2.8
Let be a commutative ring with unity. Then
is finite if and only if
is finite (and not a domain).
Proof
If is finite, then
is finite and therefore
is finite. Now, suppose
is finite. Let
be the upper basis set with
, where
is some positive integer. For any two vertices
and
of
,
by Theorem 2.5. Now, for each vertex
, the representation
is a
coordinate vector
, where each
. As each
has four possibilities, therefore the total number of possibilities for
is
. Since
is a resolving set, therefore
is unique for each vertex
so that
. This implies that
is finite and hence
is finite.□
Note that is finite if and only if
is finite, let
and let
be the upper basis. Since each coordinate of
is non-zero whenever
, we see that every coordinate in
belongs to the set
, as
. Therefore
. We note that this is a better bound than given in proof of Theorem 2.8 as
for all
.
Corollary 2.9
Let be a commutative ring with unity 1 (and not a domain) such that
, where
is any positive integer. Then
.
If is a commutative ring (and not a domain), we also notice that
gives
, thus we have a lower bound for the upper dimension of
. The equality holds when
. For a ring
,
if and only if
, that is, if and only if
,
,
.
Theorem 2.10
Let be a commutative ring with unity.
(i) |
| ||||
(ii) |
|
Proof
(i) To prove the result, we show if , then
is either a path or a cycle. For this, we first show that
, where
denotes the largest degree of a vertex in
.
We claim that there does not exist a subset of vertices in
with the property
and the restriction
, for otherwise, we have the following cases as given in . In each of the four graphs in , the bold vertices represent the set of two vertices that do not form a resolving set. Thus, the graphs
in 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
. Also, if
, then
and
. Thus, we have
. Hence
is either a path
or a cycle
or
. Therefore, we must have
or
. Since the two non-adjacent vertices of
do not form a resolving set, therefore
and so
,
,
,
.
(ii). Clearly and any subset of
vertices of complete graph forms a resolving set. Hence, the result follows by Lemma 2.2. □
Example 2.11
It is easily verified that if
,
,
,
,
, then
. However, in each case, one can find a set of two distinct vertices of
that do not form a resolving set. Thus
.
Recall that an element in a ring
is said to be nilpotent if there exists a positive integer
such that
.
Theorem 2.12
Let be a ring where every zero-divisor is nilpotent.
(i) | If | ||||
(ii) | If | ||||
(iii) | If |
Proof
(i) If , then
or
and so
. If
, then
or
or
and so
. Therefore, in each case
.
(ii) If , and
, then
for all
, by Theorem 2.8 Citation[1]. Thus,
is a complete graph and so by Lemma 2.2,
.
(iii) If and
, there exists some
such that
. So there exists
such that
. Therefore,
as
is a resolving set for any vertex
adjacent to
. □
3 Characteristic of a Ring and Star Subsets
Resolving sets for zero-divisor graphs have previously been studied in Citation[9] and [10]. In these articles, it was noted that distance similarity was a key factor in determining resolving sets. Vertices and
of a graph
are called
if
for all
. The following results illustrate this connection between concepts.
Theorem 3.1
Theorem 2.1 Citation[9] Let be a connected graph. Suppose
is partitioned into
distinct distance similar classes
(that is,
if and only if
for all
).
(i) | Any resolving set | ||||
(ii) | Each | ||||
(iii) |
| ||||
(iv) | There exists a minimal resolving set | ||||
(v) | If |
The characteristic of a ring is the least positive integer
such that
for all
, where 0 is the zero element of
. If no such integer exists, we say that
has characteristic 0.
Theorem 3.2
Let be a finite commutative ring that is not a field such that
has odd characteristic. Then
.
Proof
Since the characteristic of is odd,
and
are distance similar for any vertex
and
. Thus, by Theorem 3.1,
. □
Theorem 3.3
Let be a finite commutative ring of order 2
, where
is an odd integer. Then
.
Proof
It can be shown that for some finite ring
with odd characteristic. If
is a domain, then
is a star-graph and the result follows from Theorem 2.4. (It is also trivial to prove that
, where p is prime). Hence, we assume that
is not a domain for the rest of the proof.
The elements of can be partitioned into the sets
,
,
and
. Note that
since
and
implies
with
. Also, all elements of
are distance similar as any element of
is only adjacent to (1, 0). If
and
are distance similar vertices of
, then both
and
are distance similar in
and
and
are distance similar in
. (For example,
if and only if
if and only if
if and only if
if and only if
if and only if
). Thus, when
is partitioned into distance similar classes (as in Theorem 3.1), the only class that will have one element is
.
Next, we show (1, 0) cannot be an element of any minimal resolving set for . Suppose
is a resolving set with
. Let
. We show that
is also a resolving set. Note that
. So, let
. Then, for all
,
because (1,0) is the only vertex of
whose distance to
is 1. So, suppose
with
but
. However, since
is a resolving set, this implies
and
for all
. This is impossible if both
and
are in
, since all elements of
are distance 1 from (1, 0). If
, then
and
, for some
. Clearly,
and
. There must exist some
such that
and
. However, this implies
via the paths
and
. Hence, it must be the case that (without loss of generality)
and
. Thus
for some
. Suppose
with
for some
. Then there is some
with
. Therefore, there must be some
such that
and
are distance similar with
. However, this implies
but
. If
with
for some
, then there is some
with
. Therefore, there must be some
such that
and
are distance similar and
. Then
and
. Hence, in all cases,
.
Finally, we show that every minimal resolving set of must contain all but one element of each distance similar class. Let
be the partition of
into distance similar classes (as in Theorem 3.1). By Theorem 3.1,
for any minimal resolving set
. Therefore, assume
(that is,
) for some minimal resolving set
and some
with
.
Let and let
. As in Theorem 3.1, we will show that
is not a minimal resolving set by showing that
is a resolving set. Let
. Then
, implying there is some
with
. If
, then
and
. If
, then let
with
. Therefore,
and
are distance similar and
. Hence,
. Finally, if
with
, then
is not distance similar to
. Thus, there is some vertex
such that
. If
, there is some
such that
or
is distance similar to
. Thus,
.
However, suppose . Choose
such that
. Then, since the only vertex adjacent to
is (1, 0), we have
. Therefore,
. □
Definition 3.1
A vertex of degree one (that is, a vertex adjacent to only one other vertex) is called a . Call the vertices which are adjacent with at least one pendent vertex
and the subset of all such vertices a
. Also, the number of pendent edges incident on
is called the
of
, denoted by
. Clearly, if
denotes the degree of a vertex
, then
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 be a graph of order
with vertex set
and a star subset
such that the star degree of
is
for all
. Then
, where
.
Proof
For , choose
, and let
be pendent vertices incident on
. Then
is distance similar to
for each
and
. Therefore, by Theorem 3.1, a subset of at least
of the vertices
must be contained in any minimal resolving set. Thus any resolving set has cardinality greater than or equal to
. □
Corollary 3.5
Let be a graph as inTheorem 3.4. If, in addition,
is the zero divisor graph of some commutative ring, then
, where
.
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 such that
. For
,
with
an example of a minimal resolving set. However, it is straightforward to verify that
also defines a resolving set for
. We can see that
is minimal, as removing (1,0,0,0) would give
, removing (0,1,0,0) will give
, removing (0,0,1,0) will give
, and removing (0,0,0,1) will give
.
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 is a partition of
into distance similar sets of vertices, then a minimal resolving set is formed by taking all but one element from each
. The only exceptions are as follows.
(i) | for | ||||
(ii) | for | ||||
(iii) | for | ||||
(iv) | for |
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).
References
- AndersonD.F., LivingstonP.S., The zero-divisor graph of a commutative ring, J. Algebra, 217 1999 434–447
- BeckI., Coloring of commutative rings, J. Algebra, 116 1988 208–226
- AndersonD.D., NaseerM., Beck’s coloring of a commutative ring, J. Algebra, 159 1993 500–517
- SlaterP.J., Leaves of trees, Congr. Number., 14 1975 549–559
- HararyF., MelterR.A., On the metric dimension of a graph, Ars Combin., 2 1976 191–195
- ChartrandG., PoissonC., ZhangP., Resolvability and the upper dimension of graphs, Int. J. Comput. Math. Appl., 39 2000 19–28
- PirzadaS., An Introduction to Graph Theory 2012Universities Press, Orient Blackswan Hyderabad, India
- S. Pirzada, M. Aijaz, S.P. Redmond, On the metric and upper dimension of some graphs (submitted for publication).
- PirzadaS., RajaRameez, RedmondS.P., Locating sets and numbers of graphs associated to commutative rings, J. Algebra Appl., 1372014 1450047 (18 pp)
- RajaRameez, PirzadaS., RedmondS.P., On locating numbers and codes of zero-divisor graphs associated with commutative rings, J. Algebra Appl., 1512016 1650014 (22 pp)
- RedmondS.P., On zero divisor graphs of small finite commutative rings, Discrete Math., 307 2007 1155–1166