# On Certain Bounds for Edge Metric Dimension of Zero-Divisor Graphs Associated with Rings

Authors: Hafiz Muahmmad Afzal Siddiqui; Ammar Mujahid; Muhammad Ahsan Binyamin; Muhammad Faisal Nadeem
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Given a finite commutative unital ringS having some non-zero elements x,y such that x.y=0, the elements of S that possess such property are called the zero divisors, denoted by ZS. We can associate a graph to S with the help of zero-divisor set ZS, denoted by ζS (called the zero-divisor graph), to study the algebraic properties of the ring S. In this research work, we aim to produce some general bounds for the edge version of metric dimension regarding zero-divisor graphs of S. To do so, we will discuss the zero-divisor graphs for the ring of integers ℤm modulo m, some quotient polynomial rings, and the ring of Gaussian integers ℤmi modulo m. Then, we prove the general result for the bounds of edge metric dimension of zero-divisor graphs in terms of maximum degree and diameter of ζS. In the end, we provide the commutative rings with the same metric dimension, edge metric dimension, and upper dimension.


---

## Body

## 1. Introduction

The connection between two mainstream mathematics fields algebra and graph theory was first proposed by Beck [1]. Initially, he introduced the concept of zero-divisor graph associated to a commutative ring S, where he considered every element of a ring S as the vertices of zero-divisor graph and those two distinct vertices r and s are connected for which r⋅s=0. Observe that in this case, the 0 vertex is connected to every other vertex. In literature, this type of zero-divisor graph is denoted by ζ°S. In this work of Beck, his main idea was to present the coloring of a commutative ring. This investigation of coloring of a commutative ring was further analyzed by Anderson and Naseer in [2]. Also, they provided a counter example to Beck who conjectured that clique number clS and chromatic number χS of a ring S are the same by showing that for a finite local ring S, clS=5 and χS=6.The zero-divisor graphs by means of zero divisorsZS of a unital commutative ring S were studied by Anderson and Livingston in [3], and we will denote this type of zero-divisor graphs by ζS. This definition of zero-divisor graph is slightly different from Beck’s definition of zero-divisor graph associated to a commutative ring. Observe that, in this case, the element 0 is not considered as the vertex of zero-divisor graph, and so ζS is a subgraph of ζ°S. Anderson and Livingston presented the interplay between the ring theoretic properties of S and the graph theoretic properties of ζS; furthermore, this research provides some fundamental results related to zero-divisor graph ζS.This concept of zero-divisor graphs associated to a unital commutative ring was then extended by means of non-commutative rings by Redmond [4]. He introduced various ways to define the zero-divisor graph associated to a non-commutative ring, which includes both directed and undirected graphs. This work was then continued by Redmond [5] by means of zero-divisor graph of a commutative ring to an ideal-based zero-divisor graph of a commutative ring, where he thought of generalizing this approach by replacing elements whose product is zero with elements whose product lies in some ideal I of S. An ideal-based zero-divisor graph with the vertex set r∈S/I:rs∈Iforsomes∈S/I, where two different vertices r and s are connected if and only if their product lies in the ideal I, is denoted by ζIS. Since then, many authors have been working on this and defined the graphs such as unit graphs, zero-divisor graphs of equivalence classes, total graphs, ideal-based zero-divisor graphs, Jacobson graphs, and so on (see, for example, [5–9]). For graph theory, we refer the readers to [10, 11], and for basic definitions in ring theory, we refer the readers to [12, 13].Redmond [14] discussed all the commutative rings with unity (up to isomorphism) which produces the zero-divisor graphs on m=6,7,…,14 vertices. Moreover, an algorithm is provided to determine all commutative rings (up to isomorphism) with unity. Redmond and Szabo in [15] discussed the zero-divisor graphs of commutative rings with different metrics and upper dimensions. Ali provided a survey on antiregular graphs in [16]. The graph associated to a commutative ring is surprisingly the best demonstration of the properties of the zero-divisor set of a ring. This graph allows and helps us to figure out the algebraic properties of rings using graph theoretic approaches. The authors in [3] discussed some interesting properties of ζS. We use the way adopted by Anderson and Livingston in [3], by considering the set of non-zero zero divisors ZS as the vertex set for ζS.Throughout the paper,S is assumed to be a finite unital commutative ring, unless otherwise stated. ZS is the set of non-zero zero divisors as discussed above. A ring S is called local if it has a unique maximal ideal. The annihilator annr of an element r∈S is defined as s∈S:rs=0. An element r∈S is called nilpotent if rm=0 for some positive integer m. A ring S is called reduced if it has no non-zero nilpotent elements. ℤm=0,1,2,…,m−1 is the ring of integers modulo m, ℤmi=x+i⋅y:x,y∈ℤmandi2=−1 is the ring of gaussian integers modulo m with respect to the usual complex addition and multiplication, and Km stands for a finite field. The graph associated to the ring of Gaussian integers modulo m was introduced by Osba et al. in [17], and the zero-divisor graph of the ring of gaussian integers ℤmi is denoted by ζℤmiKelenc et al. introduced the concept of edge version of metric dimension in [18]. Consider a graph G having arbitrary vertices r and s and an edge t=rs; the mapping d:VG∪EG⟶0,1,2,3,…n−1 defined by dw,t=mindr,t,ds,t is the distance between w and t. Any two edges t1 and t2 of G are distinguished by a vertex w of G only if dw,t1≠dw,t2. Any subset S of vertex set of G is called an edge resolving set for G if every pair of edges of G is distinguished by some vertex set of S. The cardinality of the smallest edge resolving set of G is called the edge metric dimension of G and is denoted by dimEG. An edge resolving set S of a connected graph G uniquely codes all the edges of G.


## 2. Preliminaries

A graphGV,E consists of a vertex set V and an edge set E, and the number V denotes the order of G, whereas the number E denotes the size of G. An edge t∈EG relates to a pair of distinct vertices, say r and s, written as t=rs. An alternating arrangement among vertices and edges is known as a walk. If we traverse a graph G such that no vertex and edge is repeated, then it is known as a path. If the initial vertex and the terminal vertex in a path are the same, then it is known as a cycle. The distance between two distinct vertices r and s is the number of edges in the smallest path among them, and it is denoted by dr,s, and if there does not exist a path among them, we define dr,s to be infinite. If dr,s=1, then r and s are said to be neighboring vertices. The neighborhood set of a vertex r∈V is Nr=s∈V:rs∈E; furthermore, Nr=Nr∪r denotes the set of closed neighborhood of r∈V. The number Nr is the degree of the vertex r∈V which is denoted by degr or simply dr. If for every r∈V, dr=c for some fix c∈ℤ+, then the graph is said to be regular graph. The number du,t=mindu,r,du,s represents the distance between vertex u and an edge t=rs. The length of the longest path is the diameter of the graph which is denoted by diamG. Mathematically, diamG=supdr,s:r and s are distinct vertices inG.Any subsetH of vertices together with any subset of edges containing those vertices is a subgraph of a graph G; mathematically, we write H⊂G. The number of edges in the smallest cycle subgraph in a graph G is called the girth of graph, denoted by grG. The maximal complete subgraph of a graph G is called a clique which is denoted by K and K=ωG is called the clique number. If there is an edge among every pair of vertices in a graph, then it is said to be complete graph which is denoted by Km, where m is the number of vertices. If the vertices of a graph can be partitioned into two disjoint sets, say X and Y such that each vertex of X is adjacent to each vertex in Y, then the graph is said to be complete bipartite graph, and it is usually denoted by KX,Y or simply Km,n when X=m and Y=n. A cut vertex is a vertex that when removed from a connected graph creates two or more components of the graph.Kelenc et al. in [18] discussed the edge metric dimension of the path graph, complete graph, and complete bipartite graph. Since both the metric dimension and the edge metric dimension are closely related, it is feasible to find out graphs for which the metric dimension and the edge metric dimension are the same, as well as for some other graphs G for which dimG<dimEG or dimEG<dimG. In fact, Kelenc et al. were interested in exploring the comparison between the values of dimG and dimEG.The edge metric dimension of the path graphPm, cycle graph Cm, and the complete graph Km is given in the following results.Theorem 1 (see [18], Remark 1]).
For any integerm≥2, dimEPm=dimPm=1, dimECm=dimCm=2, and dimEKm=dimKm=m−1. Moreover, dimEG=1 if and only if G≅Pm.Next, it is shown that for a complete bipartite graphKr,s different from K1,1, the edge metric dimension is r+s−2.Theorem 2 (see [18], Remark 2]).
For any complete bipartite graphKr,s such that r≥1 and s≥2, dimEKr,s=dimKr,s=r+s−2.


## 3. Edge Metric Dimension of Graphs Associated with Rings

For a graphG of single vertex, the edge metric dimension is assumed to be zero and for an empty graph, the edge metric dimension is undefined. So, we begin our discussion with the following observation.Theorem 3.
LetS be a finite commutative ring with unity. Then,(i)
dimEζS is finite iff S is finite.(ii)
dimEζS is undefined iff S is an integral domain.Proof.
(i)
Suppose thatdimEζS is finite; then, there exists a minimal edge metric basis for ζS, say v1,v2,…,vt. By ([3], Theorem 2.3) diamζS≤3. So, dr,e=0,1,2or3 for every r∈VζS and e∈EζS. Hence, ZS≤4t, which implies that ZS is finite, and hence S is finite. Conversely, given that S is finite, then ZS is finite, since ZS is contained in S. So, dimEζS is finite.(ii)
As we know that edge metric dimension ofζS is undefined whenever S is an integral domain and vice versa, the assertion follows.
The following result gives the edge metric dimension of the zero-divisor graphs of a ringS whenever ζS is isomorphic to Pm for some m.Proposition 1.
LetS be a finite commutative ring with unity. Then, dimEζS=1 if and only if S is isomorphic to one of the following rings: ℤ6, ℤ8, ℤ9, ℤ2×ℤ2, ℤ3r/r2, ℤ2r/r3, or ℤ4r/2r,r2−2.Proof.
Suppose thatdimEζS=1; then, by Theorem 1, paths are the only graphs whose edge metric dimension is 1, so ζS≅Pm. Since ZS is not more than 3 whenever ζS is a path graph by ([19], Lemma 2.6), ζS is either P2 or P3.CaseI. If ζS≅P2, then ZS=a,b such that ab=0. The rings which satisfy this property are ℤ9, ℤ2×ℤ2, and ℤ3r/r2.CaseII. If ζS≅P3, then ZS=a,b,c, such that ab=0 and bc=0. The rings which satisfy this property are ℤ6, ℤ8, ℤ2r/r2, and ℤ4r/2r,r2−2 [14].
Conversely, the zero-divisor graphs of above given rings are eitherP2 or P3 [14]. Also, the zero-divisor relation is not transitive for these rings. Hence, by Theorem 1, dimEζS=1.Proposition 2.
LetS be a finite commutative ring with unity and ζS≅Cm. Then, S is isomorphic to one of these rings:(a)
ℤ3×ℤ3.(b)
K4r/r2, ℤ4r/r2+r+1,ℤ4r/2,r2,ℤ2r,s/r,s2.Proof.
Given thatS is a commutative ring with unity and ζS is a cycle graph, then by ([3], Theorem 2.4) the length of the cycle graph cannot exceed 4. We have shown the zero-divisor graphs of the above given rings in Figure 1.Figure 1
Zero-divisor graphs of above given rings.
(a)(b)Corollary 1.
LetS be a finite commutative ring with unity. Then, dimEζS=2 if S is isomorphic to one of the following rings: ℤ3×ℤ3, K4r/r2, ℤ4r/r2+r+1, ℤ4r/2,r2, ℤ2r,s/r,s2.Theorem 4.
LetS be a finite commutative ring with unity such that each r∈ZS is nilpotent.(1)
IfZS≥3 and ZS2=0, then dimEζS=ZS−1.(2)
IfZS≥3 and ZS2≠0, then dimEζS=ZS−2.Proof.
(1)
Given thatZS≥3 and ZS2≠0, then rs=0 for all r,s∈ZS, and so by ([5], Theorem 2.8), ζS is complete graph. Hence, dimEζS=ZS-1 by Theorem 1.(2)
Given thatZS≥3 and ZS2≠0, then there exist some r∈ZS such that r2≠0 which implies that there exists s∈ZS such that dr,s≥2. Hence, ZS/t,s is an edge metric generator for any vertex t adjacent to r; therefore, dimEζS≤ZS−2.
By ([20], Proposition 1), if S is a commutative ring with unity, the cut vertex of ζS is in the center of ζS. By ([20], Lemma 4), it is shown that if S is a finite commutative ring with unity, then ζS has a cut vertex of degree 1 if and only if either there is some r∈S such that annr=2 or S is isomorphic to ℤ9 or ℤ3r/r2. The next theorem provides the edge metric dimension of ζS when ζS has a cut vertex but not degree 1 vertex.Theorem 5.
LetS be a finite commutative ring with unity such that ZS≥3. If ζS has a cut vertex but no degree 1 vertex, then dimEζS=5.Proof.
LetS be a commutative ring with unity; if ζS has a cut vertex but no degree one vertex, then by ([20], Theorem 3), S is isomorphic to one of the following rings:(1)ℤ2r,sr2,s2−rs,ℤ4rr2+2r,ℤ4r,sr2,s2−rs,rs−2,2r,2s,ℤ8r,s2r,r2+4,ℤ2r,sr2,s2,ℤ4rr2,ℤ4r,sr2,s2,rs−2,2r,2s.
The zero-divisor graph associated with first four rings is given in Figure2(a), and for remaining three rings, the zero-divisor graph is given in Figure 2(b).
The minimum edge metric generator for graphs in Figures2(a) and 2(b) is given, respectively, by S1=v1,v2,v3,v4,v6 and S2=x1,x2,x3,x4,x5. Hence, in both cases, dimEζS=5.
We next determine the edge metric dimension ofζS, when ζS has exactly one vertex which is adjacent to every other vertex.Figure 2
Zero-divisor graphs of polynomial rings.
(a)(b)Theorem 6.
LetS be a finite commutative ring with unity and S≅ℤ2×K for some finite field K. Then, ζS≅K1,ZS−1 and dimEζS=ζS−2. Moreover, if S is a local ring such that ζS has no cycles, then dimEζS=1.Proof.
First, we suppose thatS is a non-local ring and S≅ℤ2×K. The set of zero divisors of S is then 1,0,0,r:r∈1,2,…,K−1 such that 1,0⋅0,r=0 for all r∈1,2,…,K−1. Observe that the vertex u=1,0 is the central vertex and is adjacent to all other ZS−1 vertices and so ζS≅K1,ZS−1. Hence, by (Theorem 2), dimEζS=ZS−2.
On the other hand, ifS is a local ring and has no cycles, then by ([20], Theorem 2.1), ζS is isomorphic to either P2 or P3, and hence dimEζS=1.Theorem 7.
LetS be a finite commutative ring with unity and S≅K1×K2, and both K1 and K2 are finite fields with |K1|=m≥3, |K2|=n≥3. Then, dimEζS=K1+K2-grζS.Proof.
Given thatS=K1×K2 is a finite commutative ring, then each vertex of the form (u, 0) of the zero-divisor graph ζS is adjacent to each (0, v) and vice versa. So, the vertex set of ζS can be partitioned into two disjoint sets, say U=u,0:u∈K1⋆ and V=0,v:v∈K2⋆. Hence, ζS≅Km−1,n−1 and grζS=4 which implies by Theorem 2 that dimEζS = K1 + K2-grζS.
We know that we can break down any positive integerm into set of prime numbers, resulting in the original number after multiplying. We are interested in finding the edge metric dimension of ζℤm when n=2p and n=pq where p and q are distinct primes. In both cases, the zero-divisor graph is the complete bipartite graph. The zero divisors of ℤm when n=pq can be partitioned into two disjoint sets by taking all the multiples of p in one set and the multiples of q in the other set.Corollary 2.
LetS be a finite commutative ring with unity and S≅ζℤm, where n=pq and p, q are distinct primes (p>2). Then, dimEζℤm=ZS−2.Proposition 3.
LetζS be a graph associated to a finite commutative ring S. Then, dimEζS=ZS−1 if ZS is an annihilator ideal.Proof.
Given thatζS is a graph associated to a commutative ring S and ZS is an annihilator ideal, then by definition for any r∈ZS, we have rs=0 for all s∈ZS, which implies that ζS is a complete graph. Hence, by Theorem 1, dimEζS=ZS−1.Proposition 4.
IfS is a finite local ring with maximal ideal μ and μ2=0, then dimEζS=ζS−1.Proof.
Given thatS is a finite local ring, JS=ZS and ZS=μ, where JS is the Jacobian radical of S which is the intersection of maximal ideals of S. Thus, ZS is a nilpotent ideal and S is not a field which implies that annZS≠0. So, annZS=ZS since μ2=0, and therefore, ζS is a complete graph. Hence, by Theorem 1, dimEζS=ζS−1.Proposition 5.
LetS be a reduced and P1, P2 be two prime ideals such that P1∩P2=0. Then, dimEζS=P1+P2 - 2 ωζS.Proof.
First, we aim to prove thatZS=P1∪P2. Suppose that r∈ZS/P1∪P2, so there exists a non-zero s∈S such that r.s=0∈P1∩P2. So, s∈P1∩P2, which is a contradiction because P1∩P2=0 as given. Also, P1∩P2⊆ZS, and hence ZS = P1∪P2. Now, we claim that ζS is a complete bipartite graph with partite sets V1=P1/0 and V2 = P2/0. Let a,b∈V1 with ab = 0. Then, ab∈P2, and therefore, either a or b∈V2, a contradiction. Thus, ζS is a bipartite graph. Now, to show that ζS is a complete bipartite graph, we take a∈V1 and b∈V2. So, ab∈P1 and ab∈P2; since both P1 and P2 are ideals, then ab∈P1∩P2=0 which implies that ab=0 and so ζS is a complete bipartite graph. Then, ωζS=2. Hence, by Theorem 2, dimEζS=P1 + P2 − 2ωζS.Theorem 8.
LetS be a finite commutative ring with unity and S≅ℤpr/r2 or S≅ℤp2, where p is a prime. Then, dimEζS=p−2.Proof.
Suppose thatS≅ℤpr/r2; then, the elements of S are of the form {ar+b: a, b∈ℤp}, and so the set of zero divisors of S is ZS = {br: b∈1,…,p−1} such that r1r⋅r2r = 0 for each r1,r2∈1,2,…,p−1. Hence, ζS≅Kp−1.
Now, ifS≅ℤp2, then its set of non-zero zero divisors is ZS = {rp: r∈1,…,p−1} such that r1p⋅r2p = 0 for each r1,r2∈1,2,…,p−1. Observe that ζS≅Kp−1, and so by Theorem 1, dimEζS=p−2.
Let us now determine the edge metric dimension of the zero-divisor graph of the ring of Gaussian integersζℤmi. As stated above, the set of Gaussian integers is of the form {r+is: r,s∈ℤ and i2=−1} and the set of Gaussian integers modulo m is of the form ℤmi = {r+is: r,s∈ℤm}. A Gaussian prime is the prime element in ℤi and the Gaussian primes can be described as(1)
1+i and 1−i are Gaussian primes.(2)
Ifp is a prime integer with p≡ 1 mod4 and p=a2+b2 for some integers a and b, then a+ib and a−ib are Gaussian primes.(3)
Ifq is a prime integer with q≡ 3 mod4, then q is a Gaussian prime.
Furthermore, ifq is a Gaussian prime, then its complex conjugate and its associates −q, iq, and −iq are also Gaussian primes. If n=p≡3mod4, then dimEζℤmi is undefined; since ℤmi is a field, ζℤmi is an empty graph.Theorem 9.
LetSbe a finite commutative ring with unity andS≅ζℤmi. Then,(1)
Forn=p2, dimEζℤmi=p2−2.(2)
Forpj≡3mod4, j=1,2dimEζℤmi=p12+p22−2ωζℤp1,p2i.(3)
Forn=p≡1mod4 with p=a2+b2, dimEζℤmi=2p−grζℤmi.Proof.
(1)
It was shown in Theorem15 [17] that n=p2ζℤmi is a complete graph, and by Theorem 1, dimEζℤmi=p2−2.(2)
Given thatp1,p2 are primes such that pj≡3mod4, for j=1,2, then ζℤp1,p2i is a complete bipartite graph, since ℤp1,p2i≅ℤp1i×ℤp2i as a direct product of two fields. Also, for a complete bipartite graph G, the clique number ωG=2, and hence by Theorem 2, dimEζℤp1,p2i=p12+p22−2ωζℤp1,p2i.(3)
Ifp≡1mod4 with p=a2+b2, then ζℤpi is a complete bipartite graph Kp−1,p−1 with partite sets a+ib/0 and a−ib/0, since ℤpi≅ℤi/p≅ℤi/a+ib×ℤi/a−ib. Also, for a complete bipartite graph G, then girth grG=2, and hence by Theorem 2, dimEζℤmi=2p−grζℤmi.Remark 1.
We know that 2 is not a Gaussian prime, since2=1−i1+i; however, 2=−i1+i2, so ℤ2i is isomorphic to the local ring ℤi/1+i2 having unique maximal ideal 0,1+i. Thus, we have Vζℤ2i=1+i, which implies that ζℤ2i is a graph with one vertex and no edges. Hence, dimEζℤ2i=0.
Now, we prove the bounds for edge metric dimension of zero-divisor graph associated to rings. Moreover, the following result gives a relation between the maximum degree, edge metric dimension ofζS, and the diameter.Theorem 10.
LetS be a finite commutative ring with unity and let ζS be its zero-divisor graph such that ZS≥5. Then,(2)log2ρ≤dimEζS≤ZS−δ,where ρ is the maximum degree and δ is the diameter of ζS.Proof.
First, we prove that⌈log2ρ⌉≤dimEζS. Let S=v1,v2,…,vr be the minimum edge resolving set for ζS. Let u∈VζS with degu=ρ and e1,e2,…,eρ be the set of all edges incident to u. For each i∈1,2,…,r, let di=mindu,v:visincidenttovi. Then, dvi,ej is di or di+1. Therefore, the size D=Dej|S:j=1,…,ρ is at most 2r. Since Dej|S≠Dek|S for j≠k, ρG≤2r, and the assertion follows.
Now, to show thatdimEζS≤ZS−δ, suppose that for u,v∈VζS, du,v=sup: dx,y⋅x,y∈ZS=δ, i.e., du,v is the diameter of ζS and let u=vo,v1,…,vδ=v be u-v path of length δ, where vo.v1=e1, v1.v2=e2, …, vδ−1.vδ=eδ. Suppose S=VζS/v1,v2,…,vδ, and since u∈S and du,ei=i−1 for i=1,…,δ, it follows that S is an edge metric generator for ζS of cardinality ZS−δ. Hence, dimEζS≤ZS−δ.
When are the metric dimension, edge metric dimension, and upper dimension the same?
In the previous section, bounds for edge metric dimension of zero-divisor graphs were given. In this section, we provide the commutative rings for which the zero-divisor graphζS has same metric dimension dimEζS, edge metric dimension dimEζS, and upper dimension dim+ζS (see Table 1).Table 1
Rings with same metric dimension, edge metric dimension, and upper dimension.
Commutative ringsSdimζS=dimEζS=dim+ζSℤ6, ℤ8, ℤ9, ℤ2×ℤ2,ℤ3r/r2, ℤ2r/r3,ℤ4r/2r,r2−21ℤ3×ℤ3,F4r/r2, ℤ4r/r2+r+1,ℤ4r/2,r2, ℤ2r,s/r,s22K1×K2, both K1 and K2are finite fields of ordergreater or equal to 3K1+K2−4ℤpr/r2 or ℤp2,where p is a primep−2


## 4. Conclusion

In this paper, we discussed the bounds for the edge metric dimension of graphs associated to commutative rings for some rings such as ring of integers modulom, polynomial rings, and the ring of Gaussian integers modulo m. Finally, we provide the general bound for edge metric dimension of zero-divisor graphs in terms of maximum degree of ζS and its diameter δ [21].



---

*Source: 5826722-2021-12-30.xml*