ISSN1842-6298 (electronic), 1843-7265 (print) Volume 15 (2020), 371 – 397
ZERO-DIVISOR GRAPHS OF FINITE COMMUTATIVE RINGS: A SURVEY
Pradeep Singh and Vijay Kumar Bhat
Abstract. This article gives a comprehensive survey on zero-divisor graphs of finite commutative rings. We investigate the results on structural properties of these graphs.
1 Introduction
The aim of this article is to survey the most recent developments in describing the structural properties of zero-divisor graphs of finite commutative rings and their applications. The zero-divisor graph of a commutative ring R, denoted by Γ(R), is the undirected graph with vertex set Z(R)∗ and two distinct vertices x and y are adjacent if xy = 0. The connection between graph theory and ring theory was established by Beck [15] in 1988. He defined a graph denoted by Γ0(R), with all the elements of a ring as vertices of the graph and two distinct verticesx andy are adjacent provided xy = 0. After modifying the definition of Beck [15], Anderson and Livingston [8] were the first who introduced the definition of zero-divisor graph.
Throughout the paper, Γ(Zn) denotes the zero-divisor graph of ring of integers modulon. Alson=pe11pe22. . . perr unless otherwise stated. Complement of graph Gis the graphGwith the vertex setV(G), such that two vertices are adjacent inGif and only if they are not adjacent in G. The line graph L(Γ(R)) of a zero-divisor graph Γ(R) is defined as a graph with vertex setV(L(Γ(R))) =E(Γ(R)) that is vertices of line graphL(Γ(R)) represents an edge of Γ(R), and distinct vertices inL(Γ(R)) are connected if and only if their corresponding edges in Γ(R) share a common vertex.
V(L(Γ(R))) ={(a, b)|a.b= 0, a and bare non-zero zero-divisors of R}
E(L(Γ(R))) ={{e1, e2} |e1 and e2 are incident to common vertex in R}
An element u is called unit if there exist element y such thatuy = 1. If there exist a unit u such that x=uy, then x and y are associates. We can partition the
2020 Mathematics Subject Classification: 05C25, 13A99, 13M99, 13P25
Keywords: commutative ring; zero-divisor graph; structural properties; Wiener index
Figure 1: Γ(Z8)
Figure 2: Γ0(Z8)
elements of V(Γ(Zn)) in such a way that two vertices are in the same class if and only if they are associates. This partition divides the elements of V(Γ(Zn)) into associate classes. We denote byAv the associate class represented by vertexv. The set of Gaussian integers, denoted by Z[i], is defined as the set of complex numbers a+bi, wherea, b∈Z. Ifx is a prime Gaussian integer, then x is either
1. (1 +i) or (1−i), or
2. q whereq is a prime integer andq ≡3(mod 4), or
3. a+bi, a−bi wherea2+b2=p, pis a prime integer and p≡1(mod 4).
For ring of Gaussian integers, we denote p and pi as prime integers which are congruent to 1 modulo 4, while q and qi are prime integers which are congruent to 3 modulo 4. For better understanding of the notation and terminology related to graph theory, one can refer to [20].
During last 20 years, many research articles have been published on associating graphs with algebraic structures. Some of them to mention are cayley graphs, conjugacy class graphs, unital graphs, conjugacy graphs, zero-divisor graphs etc.
Moreover, zero-divisor graphs were also defined and studied for non-commutative rings, near rings, semi-groups, modules, lattices and posets. In 2002, DeMeyer et al. [26] extended the study of zero-divisor graph of rings to semigroups. A detail survey of zero-divisor graph of a commutative semigroup is given in [11]. In the same year, Redmond [59] extended the definition of zero-divisor graph to non-commutative rings. He showed that for non-commutative ringR, Γ(R) is connected if the set of left and right zero-divisors coincide. Various other authors ([5], [61], [80]) investigated the properties for zero-divisor graphs of non-commutative rings. For recent survey on graphs related to algebraic structures, one can refer ([10], [11], [22]), [25], [36],
******************************************************************************
Figure 3: Γ(Z10)
Figure 4: Line graph of Γ(Z10)
[44].
In 2003, Redmond [60] took a new approach to define zero-divisor graph with the help of an idealI of a ringR. The graph ΓI(R) has vertex fromR\I, where distinct verticesx andy are adjacent if and only if xy∈I. He investigated the relationship between properties of ΓI(R) and Γ(R/I). Zero-divisor graphs of power series rings and polynomial rings were first studied by Axtell et al. [13]. He examined the diameter and girth of these rings.
In 2004, Philips et al. [55] studied the central sets in Γ(Zn) and Γ(Zn). He also investigated properties like planarity, connectivity, vertex degree etc. of Γ(Zn).
In 2005, Cordova et al. [23] extended the work of [55]. He worked on the clique and coloring of Γ(Zn) and Γ(Zn). In 2005, Aponte [12] introduced the line graph of zero-divisor graph of Γ(Zn) and studied properties like planarity, diameter, girth etc. Origin and early history of zero-divisor graph is discussed in detail in [10].
The contribution of the present work is a survey and classification of the literature on the structural properties of zero divisor graph of finite commutative ring. Our aim is to give the flavor of the subject but not be exhaustive.
The remainder of this paper is organised as follows: the structural properties like diameter, radius, girth, vertex degree, connectivity, planarity, Eulerian, Hamiltonian, and many more of zero-divisor graph for finite commutative rings is discussed in section 2. Several results on adjacency matrix, energy and eigen values are provided
in section 3. In section 4, we give some additional results related to these rings. The paper is concluded in section 5.
2 Structure in Zero-Divisor Graph of Finite Commutative Rings
In this section, we investigate the structural properties of zero-divisor graph of finite commutative rings that include-
• diameter, girth and radius
• vertex degree and connectivity
• planarity, Eulerian and Hamiltonian
• domination number and independence number
• chromatic number
We start with few definitions and terminology. A graphGiscomplete if any two distinct vertices are adjacent and is connected if there is a path between any two distinct vertices. For distinct verticesx and y inG, the distance between x and y, denoted byd(x, y), is the length of the shortest path connecting x and y.
A complete bipartite graph is a graph G which may be partitioned into two disjoint nonempty vertex sets Aand B such that two distinct vertices are adjacent if and only if they are in distinct vertex sets. A graphGiscomplete r-partite ifGis the disjoint union of r nonempty vertex sets and two distinct vertices are adjacent if and only if they are in distinct vertex sets.
In 2011, Osba [47] determined that forn=p,2q and q1q2, Γ(Zn[i]) is bi-partite and triangle free. He also showed that for anyn >2, Γ(Zn[i]) is not a tree.
The cardinality of the set of nonzero zero-divisors of Zn that is the number of vertices in Γ(Zn) and Γ(Zn) is equal ton−φ(n)−1, whereφ(n) is the number of units inZn(Lemma 6.5, [55]). For a ring of gaussian integers modulo n,|V(Γ(Zn[i]))|=
n−(22k−1×∏m
j=1(qj2αj −qj2αj−2)×∏l
s=1(pβss−pβss−1)2)−1 (lemma 12, [46]).
In 2014, Birch [18] gave a method to find the number of edges inZn[18]. Result for cardinality of the set of non-zero zero-divisors and edges for Zp1p2 ×Zq2 and Zp2 ×Zq2 are discussed in [33]. In 2006, Redmond [63] gave an algorithm to find all commutative, reduced rings with unity which gives rise to a zero-divisor graph onn vertices for anyn≥1 and a list of all commutative rings (up to isomorphism) which produce zero-divisor graph forn= 6,7, . . . ,14 vertices is also given.
******************************************************************************
2.1 Diameter, Girth and Radius
This subsection deals with the results of diameter, girth and radius of zero-divisor graph of finite commutative rings. The diameter of G is the greatest distance between any pair of vertices. The minimum among all the maximum distances between a vertex to all other vertices is considered asradius of graph G. We define girth of G denoted by g(G), as the length of the shortest cycle in G, provided G contains a cycle; otherwise g(G) =∞.
Now, we discuss the diameter and girth in zero-divisor graph. We begin with the following result given by Anderson and Livingston [8], which shows that diameter of zero-divisor graph ofZn is less than 4.
Theorem 1 (Theorem 2.3, [8]). Let R be a commutative ring. Then Γ(R) is connected and diamΓ(R)≤3. Moreover, ifΓ(R)contains a cycle, then g(Γ(R))≤7.
They noticed that all of the examples they considered had girths of 3,4 or ∞.
Based on this, they conjectured that if a zero-divisor graph has a cycle, then its girth is 3 or 4. They were able to prove this for Artinian ring (Theorem 2.4, [8]).
The conjecture was proved independently by Mulay [42] and DeMeyer and Schneider [26]. Additionally, short proofs have been given by Axtell et al. [13] and Wright [79].
Theorem 2 (Theorem 2.4, [8]). Let R be a commutative ring. If Γ(R) contains a cycle, then g(Γ(R))≤4.
In 2006, Redmond [62] gave several results on radius and centre of zero divisor graph of commutative ring. Following theorem discusses the case of commutative Artinian ring with identity.
Theorem 3. (Theorem 3.10, [62]) Let R be a commutative Artinian ring with identity that is not a domain
1. The radius of Γ(R) is zero if and only if the diameter of Γ(R) is zero if and only ifR∼=Z4 or R∼=Z2[X]/X2
2. If the radius of Γ(R) is 1, then the diameter of Γ(R) is 1 if and only if Γ(R) is complete. Otherwise, the diameter is2.
3. If the radius ofΓ(R)is2, then the diameter ofΓ(R)is2if and only ifR∼=F1× F2, where F1 and F2 are both fields and both not isomorphic to Z2. Otherwise the diameter of Γ(R) is 3.
Line graphs of zero-divisor graphs of Zn were first studied in detail by Aponte [12] in 2005. The next result gives the relation for diameter and girth of the line graph of Γ(Zn).
Diam(L(Γ(Zn))) =
⎧
⎪⎨
⎪⎩
1, ifn= 8
2, ifn≥10, r ≤2 3, otherwise.
Girth(L(Γ(Zn))) =
{3, ifn≥10
∞, ifn= 6, 8, or 9.
From this result, we can observe thatL(Γ(Zn)) is a tree if and only ifn= 6,8 or 9 (Corollary 4.2, [12]). Next we discuss properties for ring of Gaussian integers.
Theorem 4 (Theorem 12, [47]). For any integer n >1, m > 1 with n̸=q for any q,
rad(Γ(Zn[i])) =
⎧
⎪⎨
⎪⎩
0, ifn= 2
1, ifn= 2m or qm 2, otherwise.
The following result shows the diameter and girth of Γ(Zn[i]). It was shown that for primet andn >1, g(Γ(Ztn[i])) = 3 and g(Γ(Zp)) = 4
Theorem 5 (Theorem 13, [46]). Let n be a positive integer greater than 1. Then 1. diam(Γ(Zn[i])) = 1 if and only if n=q2;
2. diam(Γ(Zn[i])) = 2 if and only if n=por n= 2m with m≥2 orn=qm with m≥3.
3. diam(Γ(Zn[i])) = 3 if and only if m=pm with m≥2 or nis divisible at least by two distinct primes.
Theorem 6 (Theorem 14, [46]). Let n=∏m
j=1tnjj be the prime factorization of n.
Then:
1. If nk>1 for some k, then g(Γ(Zn[i])) = 3;
2. If nk= 1 for all k andm≥3, then g(Γ(Zn[i])) = 3;
3. If n=p1×p2 or n=p1×q or n=p1×2, then g(Γ(Zn[i])) = 3;
4. If n=q1×q2, then g(Γ(Zn[i])) = 4;
5. If n= 2×q, then g(Γ(Zn[i])) = 4.
Next we discuss the case of complement graph of gaussian integers. In 2012, Osba [48] proved that diam(Γ(Z2n[i])) = diam(Γ(Zqn[i])) = 2, n >2 and diam(Γ(Zpn[i])) = 3, n≥2. Following theorem gives the general case of diameter of (Γ(Z2n[i])).
******************************************************************************
Theorem 7 (Theorem 3, [48]). Letn >1. ifm̸=p,m̸= 2n,m̸=qn, andmis not a product of two distinct primes, then(Γ(Zm[i]))is connected with diam(Γ(Zm[i]))≤ 3.
Theorem 8 (Theorem 5, [48]). Let n be an integer such that n ̸= 2, n ̸= q, and n̸=q2. Then g(Γ(Zn[i])) = 3.
Next we present results on diameter, girth and radius of line graph of Γ(Zn[i]) given by Nazzal and Ghanem [43].
1. diam(L(Γ(Zn[i]))) = 2 if and only if n=p, 2q, q1q2, q1q2q3, 2q1q2, 4q, 2q2, 2p, qporn= 2m, qm withm≥2.
2. diam(L(Γ(Zn[i]))) = 3, otherwise.
3. girth(L(Γ(Zn[i]))) = 3.
4. radius(L(Γ(Zn[i]))) = 2.
Theorem 9 (Corollary 9.5, [43]). The centre of the graphΓ(Zn[i]) is
⎧
⎪⎨
⎪⎩
2m−1(1 +i), if n= 2m, m≥2
A(m−1)(m−1), if n=qm, m≥2
{(u, v) :u, v∈Z(Zpm)} \ {(0,0)}, if n=pm, m≥2.
.
Ghanem and Nazzal proved that L((Γ(Zn[i]))) is connected if and only if n ̸=
2, p, q2, q1q2, (see Theorem 3.1, [30]). He gave the following result for diameter and girth ofL((Γ(Zn[i]))):
1. diam(L((Γ(Zn[i])))) = 2 if n= 2m, m≥2 or n=qm, m≥3.
2. diam(L((Γ(Zn[i])))) = 3 if n = pm, m ≥ 2 or n is a composite such that n̸=q1q2.
3. girth(L((Γ(Zn[i])))) = 3 if n̸= 2, q, q2.
4. radius(L((Γ(Zn[i])))) = 2 if and only ifn̸= 2, p, q, q2 orq1q2.
Diameter and girth of direct product of rings is discussed in [14]. In 2019, Akgunes and Nacaroglu [6] calculated the diameter and girth for Zp ×Zq ×Zr. For more results on diameter and girth of zero-divisor graphs of commutative rings, readers may refer to [22].
Let B = {x ∈ Zn : pi | x for all i}. The centre of Γ(Zn) is discussed in proposition3.1−3.3 of [55].
centre(Γ(Zn)) =
⎧
⎪⎨
⎪⎩
p, ifn= 2p
Ape−1, ifn=pe (⋃r
i=1Avi)⋃
B, otherwise.
Next we discuss the centre of line graph of Γ(Zn).
Theorem 10 (Theorem 6.2, [12]). ForL(Γ(Zn)):
1. when n= 27the centre is the vertex [9,18].
2. when n= 8 the centre is L(Γ(Z8)) and the ε(v) = 1 for everyv∈L(Γ(Z8)).
3. when n= 2p the center is L(Γ(Z2p)).
4. when n= 16the center is [4,8],[8,12].
5. otherwise the center is the graph induced by the vertices with eccentricity equal to 2.
Author Graph Property
Anderson and
Livingston (1999)
Commutative ring Diameter and Girth Philips et al. (2004) Γ(Zn), Γ(Zn) | V(Γ(Zn) |, | Γ(Zn) |,
Centre
Aponte et al. (2005) L(Γ(Zn)) Diameter, Girth, Centre
Osba et al. (2008) Γ(Zn[i]) | V(Γ(Zn)[i] |, Diameter, Girth
Osba et al. (2011) Γ(Zn[i]) Radius, Bi-partite, Tree Osba et al. (2012) Γ(Zn[i]) Diameter, Girth
Nazzal and Ghanem (2012)
L(Γ(Zn[i])), Γ(Zn[i])
Diameter, Girth, Radius of L(Γ(Zn[i])) and centre of Γ(Zn[i]) Ghanem and Nazzal
(2012)
L(Γ(Zn[i])) Diameter, Girth and Radius
Birch et al. (2014) Γ(Zn) Method to find number of edges in Γ(Zn) Koam et al. (2019) Γ(Zp1p2)×Γ(Zq2),
Γ(Zq2)×Γ(Zq2)
|V |, |E |
Akgunes and
Nacaroglu (2019)
Zp×Zq×Zr Diameter, Girth and Radius
******************************************************************************
2.2 Vertex degree and connectivity
In this subsection, vertex connectivity, edge connectivity and minimum degree of zero-divisor graph of some finite commutative rings and their relationship with each other are discussed. A graphG isconnected if there is a path joining every pair of vertices. Vertex connectivity of a graph is the minimum number of vertices whose removal results in disconnection of the graph.
Degree of a vertex is the number of edges associated with it. The minimum degree of Gis the minimum degree of its vertices. A set A ⊂V(G), is said to be a cut-set if there exist distinct verticesaand binV(G)\Asuch that every path inG fromatobinvolves atleast one element fromA, and no proper subset ofAsatisfies the same condition.
The application of connectivity can be seen in communication network, for example, if we think of a graph as representing a communication network, the connectivity (or edge connectivity) becomes the smallest number of communication stations (or communication links) whose breakdown would jeopardise communication in the system. The higher the connectivity and edge connectivity, the more reliable the network.
Now we discuss the degree of vertices in zero-divisor graphs of finite commutative rings. In 2004, Philips [55] gave the relation for vertex degree in Γ(Zn), with the help of which Aponte [12] calculated vertex degree for line graph of Γ(Zn).
For any vertex u∈V(Γ(Zn)):
deg(u) =
{gcd(u, n)−1, ifu2 ̸= 0 gcd(u, n)−2, ifu2 = 0.
Also for vertexv∈V(Γ(Zn)):
deg(v) =
{n−φ(n)−gcd(v, n)−1, ifv2̸= 0 n−φ(n)−gcd(v, n), ifv2= 0.
Philips [55] showed that the vertex v1 = pe11−1pe22. . . perr in G = Γ(Zn) has minimum degree and minimum degree isδ(G) =pe11−1(p1−1)pe22. . . perr−pe11−1(p1− 1)pe22−1(p2 −1). . . perr−1(pr −1) (see, lemma 7.1). He gave a relation for vertex connectivity of Γ(Zn) in terms of minimum degree (see, Theorem 7.1- 7.2).
κ(Γ(Zn)) =
{δ(Γ(Zn)), when n=pe11pe22, e1 >1 δ(Γ(Zn))− |Av1 |+1, when n=p1pe22, e2>1.
wherev1 is the vertex of minimum degree.
Cote et al. [24], showed that a set A is a cut set of Γ(Zn) if and only if A = ann(p)\ {0} for some prime p which divides n, where n ̸= p, 2p, p2. This result was extended to Γ(∏m
i=1Zni) (Theorem 2.9, [24]).
Conjecture 11 (Conjecture 8.1, [55]). Let G= Γ(Zn) where n=pe11pe22. . . perr for primes p1 < p2 < · · · < pr. Then κ(G) = δ(G)− | Av1 | +1 when e1 = 1 and κ(G) =δ(G) when e1 >1.
The maximal degree inG(Γ(Zn)) has the vertex pn
1 and the maximum degree is equal to pn
1 −1 (cf. [70], [32]).
In 2020, Chattopadhyay and Patra [21] proved that algebraic connectivity and vertex connectivity of Γ(Zn) coincide if and only if n is a product of two distinct primes orn=pt for some primep and integert≥3. Aponte et al. [12] proved that if a graph G is connected then its line graph L(G) is also connected. In Theorem 2.1, he gave a relation for degree of vertex [u, v]∈V(L(Γ(Zn))): degL(Γ(Zn)[u, v] =
⎧
⎪⎨
⎪⎩
gcd(u, n) +gcd(v, n)−4, ifu2̸= 0 and v2̸= 0;
gcd(u, n) +gcd(v, n)−5, if either u2 = 0 or v2 = 0;
gcd(u, n) +gcd(v, n)−6, ifu2= 0 and v2= 0;
In [32], Ju and Wu proved thatκ(Γ(Zn)) =λ(Γ(Zn)) =δ(Γ(Zn)) that is, vertex connectivity, edge connectivity and minimum degree of the zero-divisor graph of ring Znalways coincide (Theorem 3.2, [32]). Also minimum degree of Γ(Zn) is discussed.
Letn=pe11pe22. . . perr for primes p1 < p2 <· · ·< pr. Then δ(Γ(Zn)) =
{p1−1, ifr >1 orr = 1, er= 2 p1−2, ifr= 1, er >2
In [58], same result for connectivity and minimum degree is proved by using a different approach. [30] gives the relation for vertex degrees of Γ(Zn[i]), and L(Γ(Zn[i])):
Theorem 12 (Theorem 10.2, [30]). Let v ∈ V(Γ(Zn[i])) and g.c.d(v, n) = c+di.
Then
deg(v) =
{c2+d2−1, ifv2 ̸= 0 c2+d2−2, ifv2 = 0.
Corollary 13(Corollary 10.3, [30]). Let[u, v]∈V(L(Γ(Zn[i]))), g.c.d(u, n) =a+bi and g.c.d(v, n) =c+di. Then
deg([u, v]) =
⎧
⎪⎨
⎪⎩
a2+b2+c2+d2−4, if u2 ̸= 0 and v2 ̸= 0 a2+b2+c2+d2−5, if u2 = 0 and v2 ̸= 0 a2+b2+c2+d2−6, if u2 = 0 and v2 = 0.
******************************************************************************
From these, one can easily compute the degrees of complement of these graphs.
It is also shown that L(Γ(Zn[i])) is regular if and only if n = p, q2, q1q2 and L(Γ(Zn[i])) is regular if and only if n =p or q3 (see, Theorem 11.4 and Theorem 11.6).
The graph Γ(Zn[i]) is regular if and only ifn= 2 orn=porn=q2(Theorem 25, [46]). Complement of graph Γ(R) is regular if and only if Γ(R) is regular. Therefore Γ(Zn[i]) is regular if and only ifn= 2 or n=p orn=q2, [48].
Also, to determine the degree of every vertex in graph Γ(Zn[i]) whenn= 2m, m≥ 2, n=qm, m≥3 and n=pm, m≥1, (see, Theorem 4-Theorem 6, [30]).
Author Graph Property
Philips et al. (2004) Γ(Zn), Γ(Zn) Vertex degree, Vertex connectivity of Γ(Zn) for some cases, Vertex of minimum degree in Γ(Zn)
Aponte et al. (2005) L(Γ(Zn)) Vertex degree Skoweonek-Kaziow
(2008)
Γ(Zn) Vertex of maximum degree Osba et al. (2008) Γ(Zn[i]) Regularity
Osba et al. (2012) Γ(Zn[i]) Regularity Ghanem and Nazzal
(2012)
Γ(Zn[i]), L(Γ(Zn[i])), L(Γ(Zn[i]))
Vertex degree of all, Regularity of L(Γ(Zn[i])) and L(Γ(Zn[i]))
Ju and Wu (2014) Γ(Zn) κ(Γ(Zn)) = λ(Γ(Zn)) = δ(Γ(Zn)), Maximum degree Reddy et al. (2018) Γ(Zn) Vertex and Edge connectivity,
Minimum degree
2.3 When a graph is Planar, Eulerian and Hamiltonian
Aplanar graph is a graph that can be drawn in a plane in such a way that its edges intersect only at their end points. The first work in this direction was given by Anderson et al. [9] in 2001, where they asked a question- Which finite commutative ringsR have Γ(R) planar? Akbari et al. [4], Smith [71], and Belshoff and Chapman [16] worked on the question posed by them on planarity of zero-divisor graphs. They give a complete list of finite commutative ringsRfor which Γ(R) is planar. For more detail, one can see section 6 of [10].
In the following theorems, we discuss the planarity of complement graph of Zn:
Theorem 14(Theorem 4.1, [55]). Γ(Zn1 × · · · ×Znr) is planar if and only ifZn1×
· · · ×Znr ∼=Zp2 for some prime p or Zn1× · · · ×Znr is isomorphic to Z2×Z2, Z2× Z3, Z8, Z2×Z4, Z2×Z2×Z2, Z3×Z3, Z2×Z5, Z4×Z3, or Z3×Z5.
Next, we discuss the planarity of zero-divisor graphs of Gaussian integers.
Theorem 15. Let Γ(Zn[i]) be a zero-divisor graph of Gaussian integers modulo n.
Then
1. (Theorem 22, [46]) The graphΓ(Zn[i]) is planar if and only if n= 2, 4.
2. (Theorem 9, [48]) Γ(Zn[i]) is planar if and only if n= 2,5 or q2.
3. (Theorem 2.3, [30]) The graphL(Γ(Zn[i])) is planar if and only if n= 5.
4. (Theorem 2.3, [43])L(Γ(Zn[i])) is never planar.
Thegenus of a graph is the minimal integernsuch that the graph can be drawn without crossing itself on a sphere with n handles. More generally, G has genus g if it can be embedded in a surface of genus g, but not in one of genus g−1. A graph G is planar if it can be embedded in the plane and is toroidal if it is not planar, but can be embedded in a torus. Let γ(G) denote the genus of G; so G is planar(resp. toroidal) when γ(G) = 0 (resp. γ(G) = 1). Genus of zero-divisor graphs of commutative rings is given in [77], [78], [76], [19].
Now we discuss the results of Eulerian and Hamiltonian graphs. A graph G is Eulerian if the graph is both connected and has a closed trail containing all edges of the graph. A graph ishamiltonian if it is connected and there exists a closed walk that visits every vertex exactly once except starting vertex without repeating the edges.
Following two theorems discuss when Γ(R) is Eulerian and Hamiltonian:
Theorem 16. Let n=pe11. . . perr. Then
1. (Theorem 3.1, [23]) Γ(Zn) is Eulerian if and only if n is odd and square-free or n= 4.
2. (Theorem 8.1, [12]) L(Γ(Zn)) is Eulerian if and only if n is odd and square- free.
3. (Theorem 8.2, [12])Γ(Zn) is Eulerian if and only ifn=p2 for some prime p.
4. (Theorem 29, [46]) The graphΓ(Zn[i])is Eulerian if and only ifn= 2 or nis a prime congruent to1modulo4 ornis a composite integer which is a product of distinct odd primes.
******************************************************************************
5. (Theorem 12, [48]) If Γ(Zn[i]) is connected, then it is Eulerian if and only if n= 2 or nis odd.
6. (Theorem 2.1, [30]) L(Γ(Zn[i])) is Eulerian if and only if n is a product of distinct odd primes.
7. (Theorem 3.2, [43])L(Γ(Zn[i])) is Eulerian graph if and only ifn= 2, p, q2, or n is a composite integer which is a product of distinct odd primes.
Theorem 17. Let n=pe11. . . perr. Then
1. (Theorem 7.1, 7.2, [23]) Γ(Zn) is Hamiltonian for n=pe11pe22 and p21p2. . . pr. 2. (Lemma 9.1, 9.2, [12])L(Γ(Zn))is Hamiltonian ifn= 2pandn=p1p2. . . pr. 3. (Corollary 11, [47])Γ(Zn[i]) is Hamiltonian if n=p or n=q2.
4. (Theorem 6.1, [30]) If n= 2m, m≥2 or n=qm, m≥3, thenL(Γ(Zn[i])) is Hamiltonian.
5. (Theorem 6.2, [30]) If n =pm, m ≥ 2 or n is a composite integer such that n̸=q1q2, then L(Γ(Zn[i])) is hamiltonian.
6. (Corollary 4.4, [43]) If n = p, 2m, qm, where m ≥ 2, or n is a composite integer which is a product of distinct odd primes thenL(Γ(Zn[i]))is Hamiltonian.
The graph Γ(Zn[i]) and Γ(Zn[i]) are locally H if and only if n = 2, p, or q2 (Theorem 1, [47], Theorem 10, [48]). If n = pm, m ≥ 1 or n is a composite integer such thatn̸=q1q2, then both Γ(Zn[i]) andL(Γ(Zn[i])) are locally connected (Theorem 5.3, [30]). From the following theorem, L(Γ(Zn[i])) is locally H if and only if n=p, q2, q1q2 and L(Γ(Zn[i])) is locallyH if and only if n=porq3.
Theorem 18 (Theorem 12.2, [30]). The following statements are equivalent 1. The graph L(Γ(Zn[i]))/L(Γ(Zn[i])) is regular.
2. The graph L(Γ(Zn[i]))/L(Γ(Zn[i])) is locally H.
Author Graph Property
Philips et al. (2004) Γ(Zn) Planarity
Aponte et al. (2005) L(Γ(Zn)), Γ(Zn) Eulerian, Hamiltonian Cordova et al. (2005) Γ(Zn) Eulerian, Hamiltonian Osba et al. (2008) Γ(Zn[i]) Planarity, Eulerian Osba et al. (2011) Γ(Zn[i]) Hamiltonian, Locally H Osba et al. (2012) Γ(Zn[i]) Planarity, Eulerian, Locally H
Ghanem and Nazzal (2012)
L(Γ(Zn[i])) Planarity, Eulerian, Hamiltonian, Locally H Nazzal and Ghanem
(2012)
L(Γ(Zn[i])) Planarity, Eulerian, Hamiltonian
2.4 Domination number and Independence number
A dominating set in a graphG is a subset of the vertex set of Gwith the property that every vertex inG is either in the dominating set or adjacent to a vertex that is in the dominating set. The domination number of G, denoted by Domn(G), is defined as the cardinality of a minimum dominating set ofG.
An independent set in a graph G is a subsetI of the vertex set of G such that no two vertices ofI are adjacent i.e. I is a subset of null vertices. Theindependence number of G, denoted by Indep(G), is defined as the cardinality of a maximum independent set of G.
Letn=pe11pe22. . . pekk where, p1, p2, . . . , pk are distinct primes and thatei’s are positive integers. Alson̸= 2p. Then domination number of Γ(Zn) isk(Theorem 1, [1]). Whenn= 2p, domination number is 1.
Proposition 19 (Proposition 5.1, [55]). Apa1
1 pa22...parr is an independent set if and only ifai ≥ e2i for alli.
In 2008, AbdAlJawad [1] gave the independence number of Γ(Zn) for n = p2, pkq, pqk, p2q2 where p < q, (see, Theorem 2-5). In 2012, Ghanem and Nazzal examined the domination number of Γ(Zn[i]) and its line graph. For L(Γ(Zn[i])), domination number is only calculated forn= 2m, qm, pm, m≥2. For domination number of Γ(Zn[i]), they gave the following theorem:
Theorem 20 (Theorem 8.2, [43]). If n = ∏k
j=1πjmj, where k ≥ 1 and πj’s are distinct gaussian prime and mj’s are positive integers and n ̸= 2 or q. Then γ(Γ(Zn[i])) =k, if nis odd, and γ(Γ(Zn[i])) =k−1, if nis even.
Theorem 21(Theorem 8.1, [30]). The domination number of complement graph of Γ(Zn[i]) is given as
1. If n̸= 2, qm, then γ(Γ(Zn[i])) = 2.
2. γ(Γ(Zq2[i])) =q2−1 and γ(Γ(Zqm[i])) =q2, m≥3.
The study of the domination number of the line graph of Gleads to the study of edge or line domination number ofG, that is,γ(L(G)) =γ′(G). Also for any graph
******************************************************************************
G, γi′(G) = γ′(G). In 2012, Ghanem and Nazzal [30] gave relation for domination number ofγ(L(Γ(Zn[i]))). γ(L(Γ(Zn[i]))) =
⎧
⎪⎪
⎪⎪
⎨
⎪⎪
⎪⎪
⎩
2m−1(2m−1−1), ifn= 2m, m≥2
1 2q2
⌊m
2
⌋ ( q
⌈m
2
⌉
−1 )2
, ifn=qm, m≥3
1 2
(
2p2m−1−p2m−2−p2m−⌈m2⌉−2 )
, ifn=pm.
Theconnected domination number of a connected graphGdenoted byγc(G), is the size of a minimum connected dominating set of a graphG. Following theorems gave the results for connected domination number:
Theorem 22 (Theorem 4.3, [65]). Let n = pe11pe22. . . pekk, where pq, p2, . . . , pk are distinct primes and the ei’s are positive integers, thenγc(Γ(Zn)) =k.
Theorem 23. For any graph Γ(Zn), γ(Γ(Zn)) = γc(Γ(Zn)) if and only if Γ(Zn) has a spanning treeT with maximum number of pendent vertices such that for every set A of pendent vertices with < A > independent of G, there exists a non-pendent vertexv in T such that A⊆N(v), where < A >, means subgraph induced by the set A.
The weak domination number of a graph G denoted by γω(G), is the minimum cardinality of a weak dominating set. In 2013, Sankar and Meena [66] calculated weak domination number of Γ(Zn) for n=p2, pq, 2n, 2np, 3n.
1. γω(Γ(Zp2)) = 1
2. γω(Γ(Zpq)) =q−1, p < q
3. γω(Γ(Z2n)) =
⎧
⎨
⎩ 2n2 ∑
n−4 2
i=0 2i+ 1, ifnis even 2n−12 ∑
n−3 2
i=0 2i, otherwise.
, n >2
4. γω(Γ(Z2np)) = 2n−1(p−1), p >2n 5. γω(Γ(Z3n)) = 3n−1−8, p >3.
In [73], point covering number, edge covering number and independence number ofL(Γ(Zn)), forn=pq, p2, p3are discussed. It is proved that edge covering number is less than the point covering number and independence number in L(Γ(Zpq)). In 2019, Abu Hijleh et al. [2] determined graph invariants matching number, vertex covering number and independence number for the zero-divisor graph over the rings Zpk and Zpkqr.
Remark 24 (Remark 1, [2]). For Γ(Zn),β(Γ(Zn)) +α(Γ(Zn)) =|V(Γ(Zn))|
Author Graph Property Philips et al. (2004) Γ(Zn) Independent set AbdAlJawad and Al-Ezeh
(2008)
Γ(Zn) Domination number Ghanem and Nazzal (2012) Γ(Zn[i]),
L(Γ(Zn[i]))
Domination number Nazzal and Ghanem (2012) Γ(Zn[i]),
L(Γ(Zn[i]))
Domination number Sankar and Meena (2012) Γ(Zn) Connected domination
number
Sankar and Meena (2012) Γ(Zn) Weak domination
number for n =
p2, pq,2n,2np,3n
Suthar and Prakash (2015) L(Γ(Zn)) Point covering number, Edge covering number, Independence number forn=pq, p2, p3
AbuHijleh et al. (2019) Γ(Zn) Matching number, Vertex covering number and Independence number for n = pk and pkqr
2.5 Chromatic Number
Beck [15] introduced the notion of coloring in a commutative ring R in 1988. The chromatic number χ(Γ0(R)) of a graph is the minimal number of colors needed to color the elements of Γ0(R) so that no two adjacent elements have the same color.
A subset {x1, x2, . . . , xn} of Γ0(R) is called a clique ifxi.xj = 0.
Beck [15] showed that for a ring R, the following conditions are equivalent: 1) χ(Γ0(R)) is finite. 2) cl(Γ0(R)) is finite. 3) the nilradical of R, nil(R), is finite and nil(R) is a finite intersection of prime ideals. He called a ring satisfying any of these three equivalent conditions a coloring. He gave a conjecture that χ(Γ0(R)) =cl(Γ0(R)) for any coloring R. Anderson and Naseer [10] gave a counter example to beck’s [15] conjecture (Theorem 2.1, [7]). They also determined the finite commutative ringsR with χ(Γ0(R)) = 4 (Theorem 7.4(c)). All finite commutative rings with clique equals to 1,2 or 3 are listed in Theorem 7.4 of [10].
Hedetniemi [31] conjectured that for all graphsGandG′,χ(G×G′) =min(χ(G), χ(G′)). In 2005, Cordova et al. [23] proved this conjecture for all Γ(Zn),χ(Γ(Zn)×
******************************************************************************
Γ(Zm)) = min(χ(Γ(Zn)), χ(Γ(Zm))). The following lemma gives the clique size in Γ(Zn).
Lemma 25 (Lemma 4.2, [23]). Let n = pe11. . . perrq1f1. . . qsfs, where pi and qj are distinct primes, such that for every1≤i≤r, ei is even, and for every1≤j ≤s, fj
is odd. In Γ(Zn) there exists a clique of size p
e1 2
1 . . . p
er
r2 q
f1−1 2
1 . . . q
fs−1
s 2 +s−1.
He also proved that for Γ(Zn), chromatic number is equal to clique number, χ(Γ(Zn)) =cl(Γ(Zn)) (see Corollary 4.3). A graphGis a core if any homomorphism from G to itself is an automorphism. Also, a subgraph H of G is called a core of G ifH is a core itself, and there is a homomorphism from G to H. Next theorem gives the core of Γ(Zn).
Theorem 26(Theorem 5.1, [23]). The core of the graphΓ(Zn)is the maximal clique in Γ(Zn).
In 2006, Duane [27] determined the chromatic number of Γ(Zn). She gave the following results in this context:
Theorem 27 (Theorem 4.9, [27]). Suppose m = p1p2. . . pn, where each pi is a distinct prime. Then Γ(Zm) is n−colorable.
Theorem 28 (Theorem 4.10, [27]). Suppose m = pa11pa22. . . pann, where each pi is a distinct prime, n ≤ 2, ai > 0 for all i, and ai > 1 for some i. Let s = p⌊a1 1/2⌋p⌊a2 2/2⌋. . . p⌊ann/2⌋. Then Γ(Zm) iss−colorable.
Corollary 29 (Corollary 4.11, [27]). If m and s are defined as in the previous theorem, then χ(Γ(Zm)) =sif at least one ai is odd. Otherwise,χ(Γ(Zm)) =s−1.
Chromatic number of Γ(Zn) is also investigated in [70], [81]. In the following theorem, Aponte et al. [12] gave a relation between vertex coloring of Γ(Zn) and chromatic number ofL(Γ(Zn)).
Theorem 30 (Theorem 7.1, [12]). In Γ(Zn), the edge leads to the vertex coloring in L(Γ(Zn)). Let n = pe11pe22. . . perr. Moreover, χ(L(Γ(Zn))) = ω(L(Γ(Zn))) =
∆(Γ(Zn)).
Following theorem gives the general formula for the chromatic number of Γ(Zn[i]):
Theorem 31(Theorem 26, [47]). Letn= 2l×(∏r
k=1qmkk×∏t
k=r+1qkmk)×(∏z
k=1pnkk×
∏c
k=z+1pnkk), mk is odd for all k≤r while mk is even integer otherwise, nk is odd for all k ≤ z while nk is even integer otherwise and let s = 2l ×∏t
k=1q2⌊
mk 2 ⌋
k ×
∏c k=1p2⌊
mk 2 ⌋ k . Then
χ(Γ(Zn[i])) =s+r+ 2z−1
Next we give results on chromatic number of line graph of zero-divisor graph of gaussian integers and their complement.
Theorem 32 (Theorem 5.1, [43]). ω(L(Γ(Zn[i]))) =χ(L(Γ(Zn[i]))) =
⎧
⎪⎨
⎪⎩
22m−1−2, if n= 2m, m≥2, q2m−2−2, if n=qm, m≥2, p2m−1−1, if n=pm, m≥1.
Theorem 33 (Theorem 5.2, [43]). If n = 2m∏r
j=1prjj∏t
j=1qj∏s
j=1qjsj, where m, rj ≥1 and sj ≥2, then
ω(L(Γ(Zn[i]))) =χ(L(Γ(Zn[i]))) = (22m−1−1)
r
∏
j=1
(p2rj j−1)
s
∏
j=1
(q2sj j−2−1)−1
Corollary 34 (Corollary 7.8, [30]). Let χ(L(Γ(Zn[i])) be chromatic number of line graph of zero- divisor graph of gaussian integers then following results holds
1. If n= 2m, m≥2, then χ(L(Γ(Zn[i])) = 22m−1−3.
2. If n=qm, m≥3, then χ(L(Γ(Zn[i]))) =q2m−2−q2−1.
3. If n=pm, m≥2, then χ(L(Γ(Zn[i]))) = 2p2m−1−p2m−2−p−1.
Author Graph Property
Cordova et al. (2005) Γ(Zn) Chromatic number, Core Aponte et al. (2005) Γ(Zn) Clique, Chromatic number
Duane (2006) Γ(Zn) Chromatic number and
Coloring
Osba et al. (2011) Γ(Zn[i]) Chromatic number Ghanem and K. Nazzal
(2012)
L(Γ(Zn)) Chromatic number Nazzal and M. Ghanem
(2012)
L(Γ(Zn)) Chromatic number Ju and M. Wu (2014) Γ(Zn) Clique number Yanjhao and Qijiao
(2015)
Γ(Zn) Clique number
******************************************************************************
3 Adjacency matrix, energy and eigen values
In this section, we discuss the results related to adjacency matrix, energy and eigen values. For any verticesxi, xj and for all i, j∈N, the adjacency matrix of the zero divisor graph Γ(R) ofR is defined as A= [Aij], where
Aij =
{1, xi, xj = 0, 0, otherwise
Adjacency matrix for zero-divisor graphs over finite ring of gaussian integer is studied by Sharma et al. [67] in 2010. Here properties like order of matrix, trace, singularity etc are discussed. In 2011, Sharma et al. [68] studied adjacency matrix ofZp×Zp and Zp[i]×Zp[i], where pis a prime.
In 2013, Patra and Baruah [50] discussed adjacency matrix of zero-divisor graph of ringsZp×Zp2, Zp×Z2p and Zp×Zp2−2. Properties like neighborhood of vertex, neighborhood number, order of matrix etc are also discussed. Laplacian eigen values of the Γ(Zn) are discussed in [21].
In [3], wiener index and energy of graph of Γ(Zn) are studied for n = pq or n=p2. A MATLAB code is also presented for same.
Energy(Γ(Zn) =
{2p−4, ifn=p2 2√
(p−1)(q−1), ifn=pq.
Wiener index(Γ(Zn) =
{(p−1)(P−2)
2 , ifn=p2
p2+q2+pq−4p−4q+ 5, ifn=pq.
f unctionGz=graph zero divisor zn2(p) n=p;
M = [];
f ori= 1 :n−1 f orj = 1 :n−1 if mod(i∗j, n) == 0 M = [M, i];
break;
end end end
n=length(M);
f ori= 0 :n−1
axes(i+ 1,:) = [cos(2∗pi∗i/n), sin(2∗pi∗i/n)];
end
Gz =zeros(n);
holdon f ori= 1 :n
plot(axes(i,1), axes(i,2),′∗′) if mod(M(i)2, p) == 0 Gz(i, i) = 1;
plot(axes(i,1), axes(i,2),′rO′) end
end
f ori= 1 :n−1 f orj =i+ 1 :n
if mod(M(i)∗M(j), p) == 0 Gz(i, j) = 1;Gz(j, i) = 1;
plot(axes([i, j],1), axes([i, j],2));
end end end
f unctions=W iener(B) B(B == 0) =inf;
A=triu(B,1) +tril(B,−1);
m=length(A);
B =zeros(m);
j= 1;
whilej <=m f ori= 1 :m f ork= 1 :m
B(i, k) =min(A(i, k), A(i, j) +A(j, k));
end end A=B;
j=j+ 1;
end
s=sum(sum(A))/2;
f unctione=energy(a) eg=eig(a);
e=sum(abs(eg));
Eigen values and wiener index of Γ(Zp3) and Γ(Zp2q) are discussed in [57].
Theorem 35 (Theorem 4.1, [57]). Let n=p3. Then the only non-zero eigenvalues of the zero-divisor graph Γ(Zn) are given by (p−1)(1±
√1+4p)
2 .
Theorem 36 (Theorem 4.3, [57]). Let n=p2q withp and q primes. Ifλ̸= 0 is a
******************************************************************************
nonzero eigenvalue of the zero-divisor graphΓ(Zn), then
λ4−(p−1)λ3−2p(q−1)2(p−1)λ2+p(p−1)2(q−1)λ+p(p−1)3(q−1)2 = 0 Wiener index of Γ(Zn)
=
{(p−12 )(2p3−3p−2), ifn=p3
1
2[p2(2p2−4p−1) +p(4p2q+ 2pq2−8pq−2q+ 5) + 2], ifn=p2q.
In [75], energy and wiener index of line graph of zero-divisor graph of Γ(Zn) for n=pq and p2 are discussed.
Energy(L(Γ(Zn)) =
{2p2−10p+ 8, ifn=p2, p≥5 4pq−8p−8q+ 16, ifn=pq.
W(L(Γ(Zn)) = {1
4(p−1)(p−2)2(p−3), ifn=p2, p≥5
1
2(p−1)(q−1)(2pq−3p−3q+ 4), ifn=pq, q > p >2.
Neighbourhood number of line graph of zero-divisor graph of Γ(Zn) is also discussed. A MATLAB program for the same is given.
Now we give relations for Hosoya polynomial and wiener index of Γ(Zpm) and Γ(Zpmq).
Theorem 37 (Theorem 2.10, [40]). H(Γ(ZPm);x) =a0+a1x+a2x2, where a0=pm−1− 1, a1= 12[(m−1)pm−mpm−1−p⌊m2⌋+ 2],anda2= 12[p2(m−1)= (m−1)pm+ (m−3)pm−1+ p⌊m2⌋]
Theorem 38 (Theorem 3.6, [40]). H(Γ(ZPmq);x) =a0+a1x+a2x2+a3x3, where a0= (p+q−1)pm−1−1,
a1=12[2mq(p−1)−(m+ 1)p+m]pm−1−12p⌊m2⌋+ 1,
a2= 12(p2+q2−1)p2m−2+12[(m−4)p−2(m−1)pq+ (2m−5)q−m+ 5]pm−1+12p⌊m2⌋, anda3= (q−1)(p−1)(p2m−2−pm−1).
W(Γ(Zn)) =
⎧
⎪⎨
⎪⎩
1
2[2p2(m−1)−(m−1)pm+ (m−6)pm−1+p⌊m2⌋+ 2], ifn=pm [p2+q2+ 3(pq−p−q) + 2]p2m−2+12[(m−3)p−
2(m+ 1)pq+ 2(m−2)q]pm−1+12p⌊m2⌋+ 1, ifn=pmq.
Hosoya polynomial and wiener index of Γ(Zpmq2) is discussed in Corollary 3.6 and theorem 3.2 of [69]. In 2019, Monius [41] investigated the spectra of Γ(Zp ×Zp ×Zp) and Γ(Zp×Zp×Zp×Zp) for some primep.
Author Graph Property
Sharma et al. (2010) Γ(Zn[i]) Adjacency matrix for some values of n
Sharma et al. (2010) Γ(Zn[i]), Γ(Zn) Adjacency matrix of Γ(Zp×Zp) and Γ(Zp[i]×Zp[i])
Ahmadi and Jahani- Nezhad (2011)
Γ(Zn) Wiener index and energy forn= p2 andpq
Patra and Baruah (2013) Direct product of Γ(Zn)
Adjacency matrix of
Zp × Zp2, Zp × Z2p and Zp×Zp2−2
Reddy et al. (2017) Γ(Zn) Eigen values and Wiener index forn=p3 andp2q
Suthar and Prakash (2018) L(Γ(Zn)) Energy and Wiener index forn= pq andp2
Mohammad and Authman (2018)
Γ(Zn) Hosoya polynomial and Wiener index forn=pm andpmq Shuker et al. (2019) Γ(Zn) Hosoya polynomial and Wiener
index forn=pmq2
Monius (2019) Γ(Zn) Spectra of Γ(Zp×Zp×Zp) and Γ(Zp×Zp×Zp×Zp)
4 Other results
By referencing a couple of other results on zero-divisor graphs, we conclude this survey article. As far as references is concerned, we restrict ourselves in the content for the most part to key references that give the reader further access to the literature; we apologize for any unintentional exclusions.
In [34], Lu and Wu determined that Γ(Zn) is end-regular if and only if n =pq or p3. Sankar et al. [64] evaluated the crossing number of Γ(Zn) for some cases of n = p2, p3. In [37], authors studied rectilinear crossing number for n =pq, pqr and 4pand compare that with crossing number. Nikmehar et al. [45] computed wiener, hyper-wiener, reverse wiener index and many more. Suthar and Parkash [73] studied the point covering number and independence number ofL(Zn), for some positive integern=p2, p3, pq. Malathi et al.
([37], [38], [39]) found the consistency of rectilinear crossing number of zero-divisor graphs ofn=p2, p3, pqand edge non-edge crossing number of Γ(Zn) forn=p3, pqrrespectively.
The properties like sum cordial labelling, geometric mean labelling and pair sum labelling of zero-divisor graph of Zn for some n is investigated in [51], [53] and [72]. Suthar and Parkash [74] studied energy, Laplacian energy, distance energy, and Wiener index of the total graph ofZnand also find the relation among these energies. In [56], Rajakumaran and Selvi determined the decomposition of Γ(Zn) into a finite number of paths and cycles for n=p2, p3. Periaswamy and Selvi in [52], [54] find the edge sum index and integral sum of zero divisor graph and studied their properties for some values ofn. In [17], strong metric dimension of the zero-divisor graphs ofZnandZn[i] is given. Compressed zero-divisor graph of commutative ring is studied in [35]. In [2] and [49], odd & even number and matching number & covering vertex number are studied.
******************************************************************************
