# The Metric Chromatic Number of Zero Divisor Graph of a RingZn

Authors: Husam Qasem Mohammad; Shaymaa Haleem. Ibrahem; Luma Ahmed Khaleel
Journal: International Journal of Mathematics and Mathematical Sciences
 (2022)

---

## Abstract

LetΓ be a nontrivial connected graph, c:VΓ⟶ℕ be a vertex colouring of Γ, and Li be the colouring classes that resulted, where i=1,2,…,k. A metric colour code for a vertex a of a graph Γ is ca=da,L1,da,L2,…,da,Ln, where da,Li is the minimum distance between vertex a and vertex b in Li. If ca≠cb, for any adjacent vertices a and b of Γ, then c is called a metric colouring of Γ as well as the smallest number k satisfies this definition which is said to be the metric chromatic number of a graph Γ and symbolized μΓ. In this work, we investigated a metric colouring of a graph ΓZn and found the metric chromatic number of this graph, where ΓZn is the zero-divisor graph of ring Zn.


---

## Body

## 1. Introduction

It is supposed thatR is a commutative ring with identity, ZR∗=ZR−0 denoted the set of all nonzero zero divisors of a ring R, and Zn is an integer ring modulo n. Kn denotes a complete graph order n while Kn,m is a complete bipartite order n+m. The cardinality of a set S symbolizes |S|. If p=ax, then we say that a divides p, or p is divisible by a, and write a|p, and if a does divide p, we write a∤p. If a ring R has exactly one maximal ideal, then R is called local. Obviously, Zn is local if and only if n=pt for positive integer t.In [1], Anderson and Livingston define a zero-divisor graph of commutative ring and denoted this concept ΓR. This graph has vertices VΓR=ZR∗ and edges EΓR=x,y∈Z∗R:xy=0; they prove ΓR is connected, dimΓR at most three, and ΓR is a finite graph if and only if R is a finite ring. This concept is a mix between two branches of mathematical graph theory and ring theory. This idea comes from Beck in [2] when he studied the coloring of commutative rings. After that, Anderson and Livingston modified this concept. From this time, many authors studied this graph and gave properties, see [3–6]. As well as, there are other studies on the zero divisor graph of ring integer modulo n, for example, see [7–10]. Also, in graph theory, Chartrand et al. define a metric chromatic number of a graph Γ and gave some basic properties [11]. Many authors studied this concept; see, for example, [12, 13].This work aims to study a chromatic number of zero divisor graphs of the ring integer modulon. Section 2 gives some basic definitions and theorems of graph theory needed. In Section 3, we study a metric colouring of a graph ΓZn and find all metric chromatic numbers of these graphs when n=pαorp1α1p2α for distinct prime numbers p,p1,p2 and positive integer numbers α,α1, andα2.


## 2. Definition and Terminologies

This section briefly discusses some definitions and theorems of the tile using graph theory.Definition 1.
(see [14]). A distance between two distinct vertices a and b in a graph Γ denotes the length of the shortest path da,b and a diameter of a graph Γ is diamΓ=maxda,b for all a,b∈Γ. While a distance da,L between a vertex a and a subset L in VΓ is minda,b:b∈L.Remark 1.
0≤da,L≤diamΓ, and da,L=0 if and only if a∈L.Definition 2.
(see [14]). A vertex coloring of a graph Γ=V,E is a function c:V⟶S such that ca≠cb for every adjacent vertices a and b in Γ and S is called available colors. The smallest integer Γ has a k−coloring. This k is called a chromatic number of Γ and symbolized XΓ. Clearly, if Γ has k−partite, then XΓ≤k.Definition 3.
(see [14]). An induced subgraph of a graph Γ that is complete is said to be a clique, and the number of the maximal clique is called the clique number and is denoted by ωΓ.Definition 4.
(see [11]).Suppose that h:Γ⟶1,2,…,n is a n−coloring of a graph Γ for a positive integer n whenever adjacent vertices may be the same colour and let the colour classifications be L1,L2,…,Ln. With each vertex a, we can associate a n−vector and a symbolized codea=v1,v2,…,vn=v1v2…vn called the metric colour code of a, where for each i with 1≤i≤n, vi=da,Li. If codea≠codeb for each pair of Γ's neighbouring vertices a and b, then h is a metric colouring of Γ. The smallest number n, for which Γ has a metric n−coloring, is said to be the metric chromatic number of Γ and is symbolized μΓ.
Clearly,μΓ is defined for every connected graph Γ and μΓ≥2 for every nontrivial connected graph Γ.Remark 2.
Leth be a proper n−coloring of a nontrivial connected graph Γ with resulting colour classes L1,L2,…,Ln and let two vertices a and b be joined by an edge in Γ. Then, a∈Li and b∈Lj for some i,j∈1,2,…,n with i≠j. Suppose that codea=v1,v2,…,vn and codeb=u1,u2,…,un. Then, vi=uj=0 and vj=ui=1. Thus, codea≠coded and h is also a metric colouring of Γ. Thus, μΓ≤χΓ.Lemma 1.
(see Observation 1.2 in [11]). For a metric colouring h of a connected graph Γ and ab∈EΓ. If da,x=db,x for each x∈VΓ−a,b, then ha≠hb.Remark 3.
(see [11]). If Γ is a complete graph order n, then μΓ=χΓ. So, if Γ is a graph containing a complete subgraph A with da,x=db,x for all x∈Γ and a,b∈A, then μΓ≥A.


## 3. Main Results

In this section, we look at a colouring code of a graphΓZn, and we find the metric chromatic number of this graph. We begin this section with Zn local ring. Firstly, we study case p3.Lemma 2.
For every prime numberp, if R≅Zp3, then ωΓR=χΓR=p.Proof 1.
By [15], ΓR≅Kp−1+Kp2−p¯; therefore, Γ(R) has Kp subgraph and p−partite graph so that ωΓR=χΓR=p.Proposition 1.
LetR≅Zp3, where p is a prime number; then, μΓR=χΓR=p.Proof 2.
SinceμΓR≤χΓR=p, so we show that μΓR≥p. Assume, to the contrary, that μΓR=p−1. Then, there is h:ΓR⟶1,2,…,p−1 is a p−1−coloring of a graph ΓR. However, we can rewrite the vertices set of a graph ΓR into the two disjoint subsets as follows: L1=xi∈ΓR:xi=ip2, i=1,2,…,p−1, and L2=yi∈ΓR−L1. If x,y∈L1 and z,w∈L2, then x=k1p2, y=k2p2, z=k3p, and w=k4p for some positive integers k1, k2, k3,k4 and k1,k2,k3 or k4 do not divide p. Therefore, x.y=k1k2p4≡0, x.z=k1k2p3≡0, and z.w,0. This implies every element in L1 adjacent to every element in L1 and L2a as well as every two elements in L2 are nonadjacent to each other. Since for all xi,xj∈L1, i,j∈1,2,…,p−1 with i≠jdxi,w=dxj,w, where w∈ΓR, then hxi≠hxj. Also, if hz=i, where z∈L2 without loss generality, say hz=1, then hz=hx1=0,1,1,…,1. However, z adjacent with x1 is a contradiction. Therefore, μΓR=p.Example 1.
LetR=Z125; then, χΓR=μΓZ125=5. We can write Z∗Z125=L1∪​L2, where L1=25,50,75,100 and(1)L2=5,10,15,20,30,35,40,45,55,60,65,70,80,85,90,95,105,110,115,120.
LetV1=25,V2=50,V3=75,V4=100, and V5=L2. Clearly, every two element x and y in L2 are nonadjacent. Then, cod25=0,1,1,1,1,cod50=1,0,1,1,1,cod75=1,1,0,1,1,cod100=1,1,1,0,1, and codx=1,1,1,1,0, for all x∈L2.
The following result shows how we can extend Proposition1 for every positive integer α≥3.Theorem 1.
LetR≅Zpα, where p is a prime number and α≥3; then,(2)μΓZpα=pα/2−pα/2−1+1,ifαiseven,pα−1/2−pα−1/2−1+2,ifαisodd.Proof 3.
We can classifyZZpα∗ as disjoint subsets Li=xipα−i:xi|p, for all i=1,2,…,α−1. When α is an even number, obviously, Li=pi−pi−1, and if 1≤i≤α/2, then Lα/2 induced a complete subgraph of ΓZpα and dx,w=dy,w, for all x,y∈Li and w∈ΓZpα. Therefore, by Lemma 1, hx≠hy, so Remark 3 leads to μΓZpα≥pα/2−pα/2−1.
We claim thatμΓZpα>pα/2−pα/2−1; if not, then there are metric pα/2−pα/2−1–coloring code of ΓZpα, say colours 1,2,…,pα/2−pα/2−1 such that xi∈Lα/2 has colour i. Now, for any vertex ∈L1, c(y) has colouring i, where 1≤i≤pα/2−pα/2−1. Since y is adjacent to every vertex in Lα/2, then hy=hxi which is a contradiction. Therefore, μΓZpα>pα/2−pα/2−1. Also, we can show ΓZpα has metric pα/2−pα/2−1+1–colouring code of ΓZpα as follows: Vi=xi:xi∈Lα/2, Vpα/2−pα/2−1+1=∪​Lt, where t=α/2+1,…,α−1. Also, since Lα/2=pα/2−pα/2−1 and ∑i=1α/2−1Li=pα/2−1−1, then Lα/2=pα/2−pα/2−1>∑i=1α/2−1Li=pα/2−1−1. Therefore, we can take every element in Lj in one independent set Vi, where j = 1, 2, …, pα/2−1, so that μΓZpα=pα/2−1−pα/2−1+1.
Ifα is an odd number, it is proved in a similar way thatα is even; we have μΓZpα>pα−1/2−pα−1/2−1+1. Also, ΓZpα has metric pα−1/2−pα−1/2−1+2 as follows: Vi=xi:xi∈Lα−1/2, Vpα/2−pα/2−1+1=Lα+1/2+1, and Vpα/2−pα/2−1+1=Lt, where t=α+1/2,α+1/2+2,…,α−1. Therefore, μΓZpα=pα−1/2−pα−1/2−1+1.
Clearly, ifn=p1p2, where p1 and p2 are distinct prime numbers, then Γp1p2 is a complete bipartite graph. So, by [11], μΓZp1p2=2. Therefore, we find μΓZ_n, whenever n=p1αp2 with p1 and p2 are distinct prime numbers and positive integer α≥2.Theorem 2.
For any two distinct prime numbersp1 and p2, μΓZp12p2=p1.Proof 4.
LetR≅Zp12p2. By [8], we can rewrite ZR∗, as disjoint subsets L1,L2,S1, and S2, where L1=x:x=kp12, L2=x:x=kp1, S1=x:x=kp2, and S2=x:x=kp1p2 for k positive integer less than α and not divided p1 or p2. We can note uv=0 if and only if u∈L1 and v∈Si or u∈S2andv∈Li or S2, for i = 1,2. Also, S2  =  p1-1.
First,ΓR has metric p1−coloring code shown as Vi=xi:xi∈S2,i=1,2,…,p1−1, S1⊆V1, and Vp1=L1∪​L2 then for all xi∈S2, hxi=1,1,…,0i,…,1; also, if y∈S1, then hy=0,0,…,0,1 and if y∈L1orL2, then hy=1,1,…,1,0. It follows that μΓR≥p1. Second, if we assume that ΓR have metric p1−1−coloring code, since for all u,v∈S2,du,w=dv,w for all w∈ΓR−u,v, then, by Lemma 1, hu≠hv. Therefore, every u∈S2 must be in different subset. So, we have at least p1−1 subsets, and for all xi∈S2, we get 1,1,…,1,0i,…,1,1. Let v∈L1, without loss of generality; we assume that v has the same colour of x1; then, hv=hx1=0,1,1,…,1,1, but v adjacent with x1 which is a contradiction. Therefore, ΓR has metric p1−coloring and μΓR=p1.
The next result affirms that we have extended Theorem2, for a ring R≅Zp1αp2 with distinct prime numbers p1,p2 and positive integer α≥2.Theorem 3.
If a ringR isomorphic with Zp1αp2, where p1andp2 are distinct prime numbers and positive integer numbers α≥2, then μΓR=m, where m=p1α/2−p1α/2−1+1,ifαiseven,p1α−1/2−p1α−1/2−1+2,ifαisodd.Proof 5.
We can rewrite the set of all zero divisors ofZp1αp2 disjoint subsets as follows:
Lp10=pm−0,Lp1i=x:x=k1p1α−i, and Lp2j=x:x=k2p1α−jp2, where 1≤i≤α−1, 1≤j≤α, and k1 and k2 are positive integers less than α with k1 not divided to p1 or p2 and k2 not divided to p1. Clearly, Lp2i=p1i−p1i−1; also, for any positive integer s, we get ∑i=1sLp2i=p1s−1. Now, in a way that is easy, we can see every two elements in a subset Lp2α/2 are adjacent and da,x=db,x, where a,b∈Lp2α/2 and x∈ZR∗−Lp2α/2; therefore, μR≥Lp2α/2=p1α/2−p1α/2−1. Also, if α is an odd number, then every x∈Lp2α/2−1 is adjacent with y, where y∈Lp2i,i∈1,2,…,α/2. So, by the same way of proof and through Theorem 2, we can show ΓR has m−coloring code of a graph ΓR and μΓR=m, where m=p1α/2−p1α/2−1+1,ifαis even,p1α−1/2−p1α−1/2+2,ifαis odd.Example 2.
Suppose thatR≅Z35.7; then, ZR∗=L30∪​L31∪​L32∪​L33∪​L34∪​L71∪​L72∪​L73∪​L74∪​L75, where(3)L30=35,35.2,35.3,35.4,35.5,35.6,L31=34,34.2,34.4,34.5,34.8,…,34.20,L32=33,33.2,33.4,33.5,33.8,33.10,…,33.62,L33=32,33.2,…,32.188,L34=3,3.3,…,3.566,L71=7.34,7.34.2,L72=7.33,7.33.2,7.33.4,7.33.5,7.33.7,7.33.8,L73=7.32,7.32.2,7.32.4,7.32.5,7.32.7,7.32.8,7.32.10,7.32.11,7.32.13,7.32.14,7.32.16,7.32.17,7.32.19,7.32.20,7.32.22,7.32.23,7.32.25,7.32.26L74=7.3,7.3.2,…,7.3.80,L75=7,7.2,7.4,7.5,…,7.242.
Sinceα=5,p1=3, and p2=7, then α/2=2 and L72=32−3=6 so that μΓR=8 :
V1=7.33,7.34,V2=7.33.2,7.34.2,V3=7.33.4,V4=7.33.5,V5=7.33.7,V6=7.33.8,V7=L74,V8=L73∪​L75∪​L3i, where, i∈1,2,3,4
We notec7.33=0,1,1,1,1,1,0,1, c7.34=0,1,1,1,1,1,1,1, c7.33.2=1,0,1,1,1,1,0,1,c7.34.2=0,1,1,1,1,1,1,1,c7.33.4=1,1,0,1,1,1,0,1,c7.33.5=1,1,1,0,1,1,0,1,c7.33.7=1,1,1,1,0,1,0,1,c7.33.8=1,1,1,1,1,0,0,1, and cx=1,1,0,0,0,0,0,1, for all x∈L74, cx=1,1,1,1,1,1,0,0 when x∈ L73, cx=0,0,0,0,0,0,0, when x∈ L75, cx=1,1,1,1,1,1,1,0, when x∈ L31orL22, cx=1,1,1,1,1,0,0, and when x∈ L33, cx=1,1,0,0,0,0,0,0 for x∈ L71.Theorem 4.
If a ringR isomorphic with Zp1αp22, where p1andp2 are distinct prime numbers and positive integer numbers α≥2, then μΓR=m, where m=p1α/2−p1α/2−1p2−1+1,ifαis even,p1α−1/2−p1α−1/2−1p2−1+2,ifαis odd.Proof 6.
If we rewriteZR∗ as Lp1p2i,1=kp1α−1p2;p1orp2,k and Lp1p2i,2=kp1α−1p22;p1orp2,k, i = 1, 2, …, α, then we have an induced complete subgraph of the set Lp1p2α/2,1 and da,x=db,x for all a,b∈Lp1p2α/2,1, x∈ZR∗. Furthermore, Lp1p2α/2,1=p1α/2−p1α/2−1p2−1>∑i=1p1α/2−1Lp1p2α/2−1,1+∑i=1p1α/2−1Lp1p2α/2−1,2=p1α/2−1−p1α/2−2+p1α/2−1−p1α/2−2p2−1=p1α/2−1p2−1. So, by the same way of proof, through Theorems 2 and 3, we obtain(4)μΓR=m,wherem=p1α/2−p1α/2−1p2−1+1,ifαis even,p1α−1/2−p1α−1/2−1p2−1+2,ifαis odd.



---

*Source: 9069827-2022-09-27.xml*