# Comments on the Clique Number of Zero-Divisor Graphs ofZn

Authors: Yanzhao Tian; Lixiang Li
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In 2008, J. Skowronek-kazio´w extended the study of the clique number ωGZn to the zero-divisor graph of the ring Zn, but their result was imperfect. In this paper, we reconsider ωGZn of the ring Zn and give some counterexamples. We propose a constructive method for calculating ωGZn and give an algorithm for calculating the clique number of zero-divisor graph. Furthermore, we consider the case of the ternary zero-divisor and give the generation algorithm of the ternary zero-divisor graphs.


---

## Body

## 1. Introduction

Abstract algebraic systems can be described more directly by studying algebraic systems with graph properties. Some of the results [1–4] showed that nonisomorphic algebraic systems have the same zero-divisor graph, which indicates that there may be some common characteristics among nonisomorphic algebraic systems. The zero-divisor graphs (ZDG) of commutative rings is a very active intersection of commutative algebra and graph theory. In 1988, Beck [5] illustrated the concept of ZDG of a commutative rings R and proved that there is a one-to-one mapping between its chromatic number χR and its clique number ωR. However, Anderson and Naseer [6] gave a counterexample on commutative local rings and denied this correspondence. By modifying the definition of the ZDG, the relationships between ZDG and commutative rings have aroused great interest among scholars [7–10]. Many different problems from bioinformatics and electrical engineering have been modeled by using cliques [11–14]. Tian et al. [15] proposed a password leak detection scheme based on a topological graph, using topological sequence to generate false user’s passwords and enhance the safety of the user’s passwords. Through the analysis of the structure of the topological graph, it was found that the zero-divisor graphs can also be applied to construct the password leak detection scheme. This scheme based on honeywords (false password) is helpful to enhance the security of password files in the system.Owing to the important properties of ZDG, some scholars have extended the relevant concepts to noncommutative rings, and some interesting results have been obtained [16, 17]. Anderson and Weber [18] investigated the ZDG of R, where R does not contain an identity. Patil and Waphare [19] characterized the ZDG of a ring with involution. Mulay [20] classified the cycle structure of the ZDG and established some group-theoretic properties of the group of graph-automorphisms. Das et al. [21] proved the upper bound of the oriented relative clique number of a planar graph to 32. Estaji and Khashyarmanesh [22] studied the properties of ZDG on finitely bounded lattices £, which are closely related to Boolean algebra. Patil and Momale [23] proved the relationship between idempotent graphs and zero-divisor graphs over a ring R. Bennis et al. [24] characterized powers of zero-divisors graph based on the parametrized family of graphs and investigated the diameter and girth of i-extended zero-divisor graphs.In the commutative ring, Anderson and Livingston [25] studied the general relationship between the graph structure properties of the ZDG and the ring structure properties of R. In 2004, Akbari and Mohammadian [26] studied the relationship between the chromatic number of GZn and its degree. Skowronek-kazio´w [27] proved the one-to-one relationship between the clique number and the maximum degree of GZn and gave the calculation method, but his result was imperfect.In this paper, we reconsidered the ZDG ofGZn and gave some counterexamples. The method of calculating clique number is constructive. In Theorem 3, the construction method of the vertex set in the maximal cliques is given. On this basis, we introduce the ternary zero-divisor graph and give the calculation formula of three factors. In Section 3, we give an algorithm for calculating the clique number and the generation algorithm of the ternary zero-divisor graph, and the validity of the algorithm can be verified by Python programming.


## 2. Main Results

A clique is a subgraph ofG, any two of its vertices are connected by edges, and the order of the maximum clique in a graph G is its clique number ωG [28, 29]. A subgraph Km with m nodes is referred to as a clique with dimension m if every two different nodes in the Km have edges connected. The minimum number of colors that can be used to color the edges of G is called the edge chromatic number, which is represented by χ1G. The maximum degree of G is represented by ΔG. The node chromatic number χG of a graph G is the minimum k for which G has a k−node coloring. The ZDG of the rings Zn is denoted by GZn, and the node-set of the graph is Zn−0, in which any two nodes x and y which have connected edges if and only if x≠y and xy≡0modn. It is found that GZn is a connected graph [30]. The graph G′ is a graph with a vertex set in Zn−0, where every two vertices x and y have connected edges if x≠y and xy≡0modn.In this section, we give some counterexamples about the clique number ofGZn, for example, let us set n=420=22·3·5·7, and through the analysis of the clique number, we find that GZ420 contains 30, 42, 70, and 210, so the clique number is 4, and let us set n=108=22·33, we find that the vertices that satisfy the definition of GZ108 are 6, 18, 36, 54, 72, and 90, so the clique number is 6. We give a method for calculating the clique number of GZn. At the same time, we give some examples. Let n=p1α1p2α2⋯psαs be the prime power factorization of n, where p1<p2⋯<ps are different primes and αi≥1, s≥1.Definition 1.
The ZDG of the ringsZn is denoted by GZn, and the node-set of the graph is Zn−0, in which any two nodes x and y have connected edges if and only if x≠y and xy≡0modn.Theorem 1 (see [28],Vizing’s theorem).
For every graphG, G≠∅, we have either χ1G=ΔG or χ1G=ΔG+1.Theorem 2 (see [27]).
The largest degree inGZn has the node n/p1, and the largest degree is n/p1−1.Theorem 3.
Ifn is a positive integer, all αi are equal to 1, then the clique number of the graph GZn is equal to s. If αi=2a (where a is a positive integer, a >1, and all 1≤i≤s), the clique number is p1α1/2p2α2/2⋯psαs/2−1. Otherwise, the clique number is(1)p1δ1/2⋯prδr/2q1β1−1/2⋯qtβt−1/2−1+t,where δii=1,…,r are even and βii=1,…,t are odd.Proof.
According to Definition1, as long as the weight product of any two vertices is a multiple of n, the result of the modular operation on n is 0, and these vertices are in the set of the zero-divisor graph clique numbers. Based on this consideration, we only need to find that the weight value product of any two vertices is a multiple of n. The problem of solving the maximal clique is transformed into the problem of solving the set of any two vertices whose weights are multiples of n. Three cases are considered, respectively.(i)
Ifn is square-free, let n=p1p2⋯ps, where pi1≤i≤s are distinct primes. We consider the set S=n/ps,n/ps−1,…,n/p1, the product of every pair elements of the set is a multiple of n, i.e., the elements of S is in the vertices set of GZn, and there are no more elements in GZn. Thus, the clique number that satisfies the condition is equal to s.(ii)
If allαi1≤i≤s are even, we investigate m=p1α1/2p2α2/2⋯psαs/2. Obviously, in the set composed of multiples of m, the product of any two elements is a multiple of n, and the set composed of these elements is the largest, that is, no larger set satisfies this feature. Then, the element m=p1α1/2p2α2/2⋯psαs/2 and the elements 2m,3m,4m,…,m−1m form a clique number of GZn. By the construction of element m, it is not difficult to find that the product mm−1 is the largest multiple of m in ring Zn, and the clique number that satisfies the condition is equal to m−1.(iii)
Ifαi are even and odd numbers, let n=p1δ1⋯prδrq1β1−1⋯qjβj−1·q1⋯qj, δi (i=1,…,r) are even, βii=1,…,j are odd, pi and qi satisfies the relation p1<p2<…<pr, q1<q2<…<qj, δi, βi, and αi satisfy the relation ∑i=1rδi+∑i=1jβi=∑i=1sαi. In the following review of the clique number discussion, we use mathematical induction, and the purpose is to prepare for the later algorithm design.
Ifj=1, n=p1δ1⋯prδrq1β1−1·q1, and let k=p1δ1/2⋯prδr/2q1β1−1/2. We consider the set A=k2,q1k,2q1k,3q1k,…,q1k−1k. The product of every pair elements of the set A is a multiple of n, i.e., the elements of A are in the vertices set of GZn. By the construction of element k, it is not difficult to find that the product q1kk−1 is the largest multiple of q1 in ring Zn, and the clique number that satisfies the condition is equal to k+1−1=k.
Ifj=2, n=p1δ1⋯prδrq1β1−1q2β2−1q1q2, and let k=p1δ1/2⋯prδr/2q1β1−1/2q2β2−1/2. We consider the set B=q1k,q2k,q1q2k,2q1q2k,3q1q2k,…,q1q2k−1k. The product of every pair elements of the set B is a product of n, i.e., the elements of B is in the vertices set of GZn. By the construction of element k, it is not difficult to find that the product q1q2k−1k is the largest multiple of q1q2 in ring Zn, and the clique number that satisfies the condition is equal to k−1+2=k+1.
Repeat the process by using mathematical induction.
Ifj=t, let c=q1q2⋯qt, and n=p1δ1⋯prδrq1β1−1⋯qtβt−1c. Let k=p1δ1/2⋯prδr/2\\q1β1−1/2⋯qtβt−1/2. We consider the set C=ck/q1,ck/q2,…,ck/qt,ck,2ck,3ck,…,ck−1k. The product of every pair elements of the set C is a multiple of n, i.e., the elements of C is in the vertices set of GZn. By the construction of element k, it is not difficult to find that the product ck−1k is the largest multiple of c in ring Zn, and the clique number that meets the condition is k−1+t. Of course, the number j∈N.
Through the above analysis, we conclude that the number of elements satisfying the condition is equal to(2)p1δ1/2⋯prδr/2q1β1−1/2⋯qtβt−1/2−1+t.
The proof is complete.We give some examples of calculating the number of the clique number in the ZDG, and the validity of the algorithm can be verified by Python programming.In this paper, we present ZDG forGZn by Python. Figure 1 shows the structure of the ZDG of GZ20, which is completely symmetric. The clique number of ZDG of GZ20 is 2, and the sets that satisfy the zero-divisor condition are GZ201 = \{2, 10\}, GZ202 = \{6, 10\}, GZ203 = \{14, 10\}, GZ204 = \{18, 10\}, GZ205 = \{4, 10\}, GZ206 = \{8, 10\}, GZ207 = \{12, 10\}, GZ208 = \{16, 10\}, GZ209 = \{4, 5\}, GZ2010 = \{5, 8\}, GZ2011 = \{5, 12\}, GZ2012 = \{5, 16\}, GZ2013 = \{4, 15\}, GZ2014 = \{8, 15\}, GZ2015 = \{12, 15\}, and GZ2016 = \{15, 16\}. There are 16 sets that satisfy this condition, and these sets are isomorphic. Figure 2 shows the structure of the ZDG of GZ30, which is also completely symmetric. The two-way arrow indicates that the condition of ZDG of GZ30 is satisfied between two points, where the triangle formed by the bold line is the element of the number of clusters of the ZDG of GZ30, which include 10, 12, and 15. Figure 3 shows the structure of the ZDG of GZ49, which include 7, 14, 21, 28, 35, and 42. Figure 4 shows the structure of the ZDG of GZ90. The number of elements which satisfying the condition is 4, which include 6, 30, 45, and 60.Figure 1
Zero-divisor graphs ofGZ20.Figure 2
Zero-divisor graphs ofGZ30.Figure 3
Zero-divisor graphs ofGZ49.Figure 4
Zero-divisor graphs ofGZ90.To further investigate the properties of the zero-divisor graphs, we generalize the number of zero-divisor graphs satisfying Definition1 to three, namely, all zero-divisor graphs satisfying equation xyz≡0modN, where N is a positive natural number; the product of any three positive natural numbers is a multiple of N; after the product takes the modulus of N, the result is zero, which we call zero-divisor. The three zero-divisor elements x,y,z represent the weight values of vertices and edges in graph G, respectively.Definition 2.
The zero-divisor graph of the ringsZN is denoted by GZN, and the node-set of the graph is ZN−0, in which any three nodes x, y, and z have connected edges if and only if x≠y≠z and xyz≡0modN,x,y,z,N∈N∗,1<x<N, 1<y<N, and 1<z<N. In the triple x,y,z, we specify that the first element and the third element represent two vertices of the zero-divisor graph, and the second element represents the edge weight values of the zero-divisor graph.Theorem 4.
Suppose1<x<N, 1<y<N, and 1<z<N are positive integers, where x, y, and z are different from each other and satisfy the following 3-tuples congruence equation:(3)xyz≡0modN,N∈N∗.
WhenN is taken of different values, the number of triples x,y,z formed by the solutions to equation (3) is given by(4)GN=0Nis primer12p4−116p3+p2+73p−2N=p276p6−52p5+12p3+73p2+12p−2N=p32p8−4p7+76p6−12p5+52p3+56p2−2N=p4172p4q2r2−9p4q2r−9p4qr2−12p3q2r2+3p4q2+9p4qr+3p4r2+12p3q2r+12p3qr2+92p2q2r2−3p4q−3p4r−4p3q2−14p3qr−4p3r2−92p2q2r−92p2qr2+p4+5p3q+5p3r+32p2q2−p2qr+32p2r2−116p3+52p2q+52p2r+6pqr−32p2−3pq−3pr+73p−2N=p2qr112p4q4−8p4q3−8p3q4+3p4q2+616p3q3+3p2q4−92p3q2−92p2q3+12p3q−p2q2+12pq3+72p2q+72pq2−53pq−2N=p2q2.
For the sake of convenience, the symbolA represents the set of solutions for all the positive integers satisfying the 3-tuples congruence equation, GN represents the number of elements in the set A, S represents the set that contains i, 2≤i<N, ∁SB represents the set that contains i, i∈B,  i∈S, and Ap represents the set that contains multiple of p.Proof.
IfN<6, according to Definition 2, it is not difficult to find that set A is empty. N is a prime number, and then set A is empty.
The following assumes thatN is a composite number, according to the fundamental arithmetic theorem, and we have the standard decomposition of N which is(5)N=p1α1p2α2⋯psαs,where p1<p2<⋯<ps are different primes and αi≥1, i∈1,s.
We discuss the value ofGN in the following situations, and the method discussed is similar when N takes other values. According to the prime factorization of integer N, we divide the elements in the interval 2,N into two disjoint sets and select the elements from different sets to generate the multiple of N. Obviously, the product of elements satisfying the multiple of N also satisfies equation (1). Based on this idea, we have the following discussion:(i)
N=p2The number of elementsAp is p−1. Since i∈S, 2≤i<p2, the number of elements S is p2−2, and the number of elements ∁SAp is p2−p−1. By the permutation and combination formula, we can get(6)GN=CAp2C∁SAp1+CAp3=12p4−116p3+p2+73p−2.In this case,GN is calculated from equation (6).(ii)
N=p3The number of elementsAp is p2−p. Since i∈S, 2≤i<p2, the number of elements S is p3−2, and the number of elements ∁SAp is p3−p2−1. By the permutation and combination formula, we can get(7)GN=CAp3+CAp23+CAp22C∁SAp∪Ap21+CAp1CAp22+C∁SAp∪Ap21CAp1CAp21+CAp2CAp21=76p6−52p5+12p3+73p2+12p−2.In this case,GN is calculated from equation (7).(iii)
N=p4The number of elementsAp is p3−1, the number of elements Ap2 is p2−1, the number of elements Ap3 is p−1, and the number of elements ∁SAp is p4−p3−1. By the permutation and combination formula, we have(8)GN=CAp33+C∁SAp1+CAp−Ap21+CAp2−Ap31CAp32+C∁SAp1CAp−Ap21CAp31+C∁SAp1CAp2−Ap31CAp31+CAp−Ap21CAp2−Ap31CAp31+CAp−Ap22CAp31+CAp2−Ap32CAp31+CAp2−Ap33+CAp3−Ap21CAp2−Ap2+CAp4−Ap3−11CAp2−Ap2+CAp3−Ap22CAp2−Ap1=2p8−4p7+76p6−12p5+52p3+56p2−2.In this case,GN is calculated from equation (8).(iv)
N=p2qrThe number of elementsAp is pqr−pq−pr−qr+p+q+r−1, the number of elements Aq is p2r−p2−pr+p, the number of elements Ar is p2q−p2−pq+p, the number of elements Ap2 is qr−q−r+1, the number of elements Apq is pr−p−r+1, the number of elements Apr is pq−p−q+1, the number of elements Aqr is p2−p, the number of elements Ap2q is r−1, the number of elements Ap2r is q−1, the number of elements Apqr is p−1, the number of elements ∁SAp∪Aq∪Ar∪Ap2∪Apq∪Apr∪Aqr∪Ap2q∪Ap2r∪Apqr is p2qr−p2q−p2r−pqr+p2+pq+pr−p−1. For the sake of writing conveniently, ∁SAp∪Aq∪Ar∪Ap2∪Apq∪Apr∪Aqr∪Ap2q∪Ap2r∪Apqr is abbreviated as AT, DA1 represents the set Ap,Ap2,Apq,Apr,Ap2q,Ap2r, DA2 represents the set Aq,Apq,Aqr,Ap2q, DA3 represents the set Ar,Apr,Aqr, DA4 represents the set Ar,Apr,Aqr,Ap2r,Apqr, DA5 represents the set Aq,Apq,Aqr,Ap2q,Apqr, DA6 represents the set Ap2,Ap2q,Ap2r, DA7 represents the set Ar,Apr,Aqr,Ap2r,Apqr, DA8 represents the set Aq,Apq,Aqr,Ap2q,Apqr, DA9 represents the set Ap,Aq,Ar,\\Ap2,Apq,Apr,Aqr,Ap2q,Ap2r, DA10 represents the set Apr,Aqr,Ap2r,Apqr, DA11 represents the set Aqr,Ap2q,Apqr, DA12 represents the set Ap2q,Ap2r,Apqr, DA13 represents the set Apr,Ap2r,Apqr, DA14 represents the set Apq,Aqr,Ap2q,Apqr, DA15 represents the set Apr,Ap2q,Ap2r,Apqr, DA16 represents the set Aqr,Ap2q,Ap2r,Apqr, and DA17 represents the set Apr,Aqr,Ap2q. By the permutation and combination formula, we have(9)GN=ATCApqr2+Apqr∑i∈DA1Ci1+Ap2r∑i∈DA2Ci1+Ap2q∑i∈DA3Ci1+Ap2Aqr+ApqApr+CApqr3+CAp2Aqr+Apqr+CAq2Ap2r+CAr2Ap2q+CAp22Aqr+Apqr+CApq2∑i∈DA4Ci1+CApr2∑i∈DA5Ci1+CAqr2∑i∈DA6Ci1+CAp2q2∑i∈DA7Ci1+CAp2r2∑i∈DA8Ci1+CApqr2∑i∈DA9Ci1+CAp1CAq1Apr+Ap2r+Apqr+CAp1CAr1Apq+Ap2q+Apqr+CAp1CAp21Aqr+Apqr+CAp1CApq1∑i∈DA10Ci1+CAp1CApr1∑i∈DA11Ci1+CAp1CAqr1∑i∈DA12Ci1+CAp1CAp2q1Ap2r+Apqr+CAp1CAp2r1Apqr+CAq1CAr1∑i∈DA6Ci1+CAq1CAp21∑i∈DA10Ci1+CAq1CApq1∑i∈DA13Ci1+CAq1CApr1∑i∈DA12Ci1+CAq1CAqr1Ap2q+Ap2r+CAq1CAp2q1Ap2r+Apqr+CAq1CAp2r1CApqr1+CAr1CAp21∑i∈DA14Ci1+CAr1CApq1∑i∈DA15Ci1+CAr1CAp2q1∑i∈DA10Ci1+CAr1CApr1CApqr1+CAqr1CAp2r1+CAp2r1CApqr1+CAp21CApq1∑i∈DA10Ci1+CAp21CApr1∑i∈DA11Ci1+CAp21CAqr1∑i∈DA12Ci1+CAp21CAp2q1CAp2r1+CApqr1+CAp21CAp2r1CApqr1+CApq1CApr1∑i∈DA16Ci1+CApq1CAqr1∑i∈DA12Ci1+CApq1CAp2q1Ap2r+Apqr+CApq1CAp2r1CApqr1+CApr1CAqr1∑i∈DA12Ci1+AprAp2q+AqrAp2qAp2r+Apqr+CAp2r1CApqr1∑i∈DA17Ci1=172p4q2r2−9p4q2r−9p4qr2−12p3q2r2+3p4q2+9p4qr+3p4r2+12p3q2r+12p3qr2+92p2q2r2−3p4q−3p4r−4p3q2−14p3qr−4p3r2−92p2q2r−92p2qr2+p4+5p3q+5p3r+32p2q2−p2qr+32p2r2−116p3+52p2q+52p2r+6pqr−32p2−3pq−3pr+73p−2.In this case,GN is calculated from equation (9).(v)
N=p2q2The number of elementsAp is pq2−q2−pq+q, the number of elements Aq is p2q−p2−pq+p, the number of elements Apq is pq−p−q+1, the number of elements Apq2 is p−1, the number of elements Ap2q is q−1, the number of elements Ap2 is q2−q, and the number of elements Aq2 is p2−p. CA1 represents the set Ap,Aq,Aq2,Ap2,CA2 represents the set Aq,Ap2,Apq,Ap2q, CA3 represents the set Aq2,Apq,Apq2, CA4 represents the set Aq,Apq,Ap2q, CA5 represents the set Aq,Apq,Apq2, CA6 represents the set Aq,Ap2,Aq2,Apq,Ap2q, CA7 represents the set Ap2,Aq2,Apq,Apq2, and CA8 represents the set Ap,Aq,Apq,Apq2,Ap2q,Ap2,Aq2. The number of elements ∁SCA8 is p2q2−2−CA8. By the permutation and combination formula, we have(10)GN=CS3−C∁SCA83−C∁SCA82∑i∈CA8Ai−C∁SCA81∑i∈CA1Ci2+CAp1∑i∈CA6Ci1+CAq1∑i∈CA7Ci1+CAp21CApq1+CAp21CAp2q1+CAq21CApq1+CAq21CApq21−C∁SCA80∑i∈CA1Ci3+CAp2∑i∈CA2Ci1+CAp1CAq2+CAp22+CAq22+CAq1CAp21+CAq1CAq21+CAp21CApq1+CAp21CAp2q1+CAq2∑i∈CA3Ci1+CAp22∑i∈CA4Ci1+CAq22∑i∈CA5Ci1+CAq1CAq21CApq1+CAq1CAq21CApq21=112p4q4−8p4q3−8p3q4+3p4q2+616p3q3+3p2q4−92p3q2−92p2q3+12p3q−p2q2+12pq3+72p2q+72pq2−53pq−2.In this case,GN is calculated from equation (10). This completes the proof.In Figures5–8, the zero-divisor graphs corresponding to different N are given. With the increase of N, the number of edges of the zero-divisor graphs shows a rapid increase trend, but the number of the corresponding maximum clique does not change significantly, which indicates that the zero-divisor graphs are characterized by sparsity. The clique number of GZ21 is 5. The vertices set of maximal clique is 2,7,9,14,18. The set of maximal clique elements is 2,6,7,2,7,9,2,6,14,2,7,18,7,8,9,7,12,14,7,9,18,9,12,14,\\9,14,18,14,16,18. The clique number of GZ25 is 4. The vertices set of maximal clique is 2,10,15,20. The set of maximal clique elements is 2,5,10,2,15,20,2,10,15,\\10,13,20,10,14,15,15,18,20. The clique number of GZ34 is 3. The vertices set of maximal clique is 2,17,19. The set of maximal clique elements is 2,5,17,2,17,19,17,\\18,19. The clique number of GZ12 is 5. The vertices set of maximal clique is 2,4,6,8,10. The set of maximal clique elements is 2,3,4,2,5,6,2,3,8,2,9,10,4,5,6,4,6,8,\\4,6,10,6,7,8,6,8,10,8,9,10.Figure 5
Zero-divisor graphs ofGZ21.Figure 6
Zero-divisor graphs ofGZ25.Figure 7
Zero-divisor graphs ofGZ34.Figure 8
Zero-divisor graphs ofGZ12.


## 3. The Clique Number Algorithm and Some Examples

### 3.1. Clique Number Algorithm

The Clique number algorithm is detailed in Algorithm1. The speed at which the clique number on the ring Zn is solved depends on the prime factorization of the integer. If the integer is a composite number, according to the discussion of Theorem 3, the clique number is solved in three cases, in one case, the indexes are all 1, in the second case, the indexes are all even, and in the third case, the number of odd and even indexes is at least 1. It is not difficult to find that the number of the clique number is closely related to the prime factors and indicators of integers. The zero-divisor graph of three factors is given by Algorithm 2, and the formula of the solution of the ternary is given by Theorem 4. We find that the complexity of solving zero-divisor is increasing rapidly with the difference of the number and index of prime factors.Algorithm 1: Clique number algotithm.
Input: integer NOutput: the clique number(1)
Pollard Rho Prime FactorizationN=p1α1p2α2…pnαn (pi is prime, αi is index).(2)
ifN is a composite number then(3)
ifαi = 1(i = 1 to n) then(4)
The clique number is the number of prime factors n.(5)
else ifαi mod 2 ≡ 0 (i = 1 to n) then(6)
The clique number is p1α1/2p2α2/2⋯pnαn/2−1.(7)
else ifαi mod 2 ≡ 0 (i =1 to n) and αj mod 2 ≡ 1 (j =1 to n) and αi≥1 and αj≥1then(8)
The clique number is p1δ1/2⋯prδr/2q1β1−1/2⋯qtβt−1/2+t−1 (r is the number of prime factors that are odd, and t is the number of prime factors that are even).(9)
else(10)
Integer N is prime, and the clique number does not exist.(11)
end if(12)
end ifAlgorithm 2: Generating the zero-divisor graph GZN.
Input: the sets B1 and B2 produced by equation (1)Output: zero-divisor graph GZN.(1)
Initialization: set the operations (intersection, union and difference, symmetric difference, etc.) on setsB1 and B2 to generate the vertex set V=v1,v2,…,vn.(2)
fori=1 to Vdo(3)
vi⟵Vmin(4)
forj=1 to V−Vido(5)
if weight vivjk≠ weight (vivjs) then(6)
Generate the edge set: Ei⟵eiej1,…,eiejm⊳m is the number of vertices connected to vi, Vi is the set of vertices with the smallest labeling.(7)
else(8)
vj⟵minlabelingvjk,labelingvjs,(9)
return Step 6.(10)
end if(11)
end for(12)
end for(13)
returnGZN.


### 3.2. Examples

(1)
Ifn=30=2·3·5, based on Theorem 3, the clique number of GZ30 satisfying the condition is 3. The vertices set of GZ30 is GZ30=6,10,15.(2)
Ifn=60=22·3·5, based on Theorem 3, the clique number of GZ60 that meets the criteria is 3. The vertices set of GZ60 is GZ60=12,20,30.(3)
Ifn=196000=25·53·72, then based on Theorem 3, the clique number of GZ196000 that meets the criteria is 141.(4)
Ifn=231525=33·52·73, then based on Theorem 3, the clique number of GZ231525 satisfying the condition is 106.(5)
Ifn=225+1=641·6700417, then based on Theorem 3, the clique number of GZ4294967297 satisfying the condition is 2. The vertices set of GZ4294967297 is 641,6700417.


## 3.1. Clique Number Algorithm

The Clique number algorithm is detailed in Algorithm1. The speed at which the clique number on the ring Zn is solved depends on the prime factorization of the integer. If the integer is a composite number, according to the discussion of Theorem 3, the clique number is solved in three cases, in one case, the indexes are all 1, in the second case, the indexes are all even, and in the third case, the number of odd and even indexes is at least 1. It is not difficult to find that the number of the clique number is closely related to the prime factors and indicators of integers. The zero-divisor graph of three factors is given by Algorithm 2, and the formula of the solution of the ternary is given by Theorem 4. We find that the complexity of solving zero-divisor is increasing rapidly with the difference of the number and index of prime factors.Algorithm 1: Clique number algotithm.
Input: integer NOutput: the clique number(1)
Pollard Rho Prime FactorizationN=p1α1p2α2…pnαn (pi is prime, αi is index).(2)
ifN is a composite number then(3)
ifαi = 1(i = 1 to n) then(4)
The clique number is the number of prime factors n.(5)
else ifαi mod 2 ≡ 0 (i = 1 to n) then(6)
The clique number is p1α1/2p2α2/2⋯pnαn/2−1.(7)
else ifαi mod 2 ≡ 0 (i =1 to n) and αj mod 2 ≡ 1 (j =1 to n) and αi≥1 and αj≥1then(8)
The clique number is p1δ1/2⋯prδr/2q1β1−1/2⋯qtβt−1/2+t−1 (r is the number of prime factors that are odd, and t is the number of prime factors that are even).(9)
else(10)
Integer N is prime, and the clique number does not exist.(11)
end if(12)
end ifAlgorithm 2: Generating the zero-divisor graph GZN.
Input: the sets B1 and B2 produced by equation (1)Output: zero-divisor graph GZN.(1)
Initialization: set the operations (intersection, union and difference, symmetric difference, etc.) on setsB1 and B2 to generate the vertex set V=v1,v2,…,vn.(2)
fori=1 to Vdo(3)
vi⟵Vmin(4)
forj=1 to V−Vido(5)
if weight vivjk≠ weight (vivjs) then(6)
Generate the edge set: Ei⟵eiej1,…,eiejm⊳m is the number of vertices connected to vi, Vi is the set of vertices with the smallest labeling.(7)
else(8)
vj⟵minlabelingvjk,labelingvjs,(9)
return Step 6.(10)
end if(11)
end for(12)
end for(13)
returnGZN.


## 3.2. Examples

(1)
Ifn=30=2·3·5, based on Theorem 3, the clique number of GZ30 satisfying the condition is 3. The vertices set of GZ30 is GZ30=6,10,15.(2)
Ifn=60=22·3·5, based on Theorem 3, the clique number of GZ60 that meets the criteria is 3. The vertices set of GZ60 is GZ60=12,20,30.(3)
Ifn=196000=25·53·72, then based on Theorem 3, the clique number of GZ196000 that meets the criteria is 141.(4)
Ifn=231525=33·52·73, then based on Theorem 3, the clique number of GZ231525 satisfying the condition is 106.(5)
Ifn=225+1=641·6700417, then based on Theorem 3, the clique number of GZ4294967297 satisfying the condition is 2. The vertices set of GZ4294967297 is 641,6700417.


## 4. Conclusions

Through the induction and classification discussion methods, we simplified the calculation of the clique number and constructed an algorithm to calculate the clique number in the ZDG. Through analysis, it is found that the ZDG satisfies the properties of high symmetry and degree centrality. The so-called degree centrality refers to that a very large scale of edges are connected by very few vertices, at the same time, other edges are joined by very few vertices. Furthermore, we discussed the calculation of the ternary zero-divisor graph and gave the algorithm of the ternary zero-divisor graph. By analyzing Theorem4, we found that the number of zero-divisor solutions is given by fractional polynomials, and the complexity of solving zero-divisor solutions increases rapidly with the increase of the number of prime factors.



---

*Source: 6591317-2022-03-29.xml*