# Zero-Divisor Graphs of $\mathbb{Z}_{n}$, their products and $D_{n}$

Amrita Acharyya  Department of Mathematics and Statistics
University of Toledo, Main Campus
Toledo, OH 43606-3390<EMAIL_ADDRESS>and  Robinson Czajkowski
Department of Mathematics and Statistics
University of Toledo, Main Campus
Toledo, OH 43606-3390<EMAIL_ADDRESS>
###### Abstract.

This paper is an endeavor to discuss some properties of zero-divisor graphs of
the ring $\mathbb{Z}_{n}$, the ring of integers modulo $n$. The zero divisor
graph of a commutative ring $R$, is an undirected graph whose vertices are the
nonzero zero-divisors of $R$, where two distinct vertices are adjacent if
their product is zero. The zero divisor graph of $R$ is denoted by
$\Gamma(R)$. We discussed $\Gamma(\mathbb{Z}_{n})$’s by the attributes of
completeness, k-partite structure, complete k-partite structure, regularity,
chordality, $\gamma-\beta$ perfectness, simplicial vertices. The clique number
for arbitrary $\Gamma(\mathbb{Z}_{n})$ was also found. This work also explores
related attributes of finite products
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$, seeking to
extend certain results to the product rings. We find all
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ that are
perfect. Likewise, a lower bound of clique number of
$\Gamma(\mathbb{Z}_{m}\times\mathbb{Z}_{n})$ was found. Later, in this paper
we discuss some properties of the zero divisor graph of the poset $D_{n}$, the
set of positive divisors of a positive integer $n$ partially ordered by
divisibility.

###### Key words and phrases:

zero-divisor graph, commutative ring, finite products, poset, type graph

###### 2010 Mathematics Subject Classification:

68R10, 68R01, 03G10, 13A99

##  1\. Introduction

Zero-divisor graphs were first discussed by Beck [1] as a way to color
commutative rings. They were further discussed by Livingston and Anderson in
[4] and [5]. A zero-divisor graph of a ring $R$, denoted by $\Gamma(R)$, is a
graph whose vertices are all the zero divisors of $R$. Two distinct vertices
$u$ and $v$ are adjacent if $uv=0$. Beck [1] considered every element of $R$ a
vertex, with 0 sharing an edge with all other vertices. Since then, others
have chosen to omit 0 from zero-divisor graphs [2, 3, 4, 5]. For our purposes,
we omit 0 so that the vertex set of $\Gamma(\mathbb{Z}_{n})$ denoted by
$ZD(\mathbb{Z}_{n})$ will only be the non-zero zero-divisors.
In the first section, we explore a concept explored by Smith [3] called type
graphs. In [3], type graphs were used to find all perfect
$\Gamma(\mathbb{Z}_{n})$. We extended the notion of type graphs for
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ to find all
perfect zero-divisor graphs of such products, where $n_{1},n_{2},\cdots,n_{k}$
are positive integers and
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ is the direct
product of $Z_{n_{i}}$s, $1\leq i\leq k$. We then move on to various
properties of $\Gamma(\mathbb{Z}_{n})$ and
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$. AbdAlJawad
and Al-Ezeh [2] discussed the domination number of $\Gamma(\mathbb{Z}_{n})$.
We extend this result to find an upper bound and lower bound for the
domination number of finite product
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ and discussed
coefficient of smallest degree of domination polynomial of
$\Gamma(\mathbb{Z}_{n})$. In the last section, we explore zero divisor graphs
of the poset $D_{n}$, the set of positive divisors of a positive integer $n$
partially ordered by divisibility and we catalog them in a similar way. Zero
divisor graph of poset is studied in [8], [9], [10].

##  2\. Type Graphs

When we consider zero-divisor graphs of $\Gamma(\mathbb{Z}_{n})$, it is useful
to consider the type graphs of these rings. A type graph has vertices of
$T_{a}$ where $a$ is a factor of $n$ that is neither 1 nor 0. The set of all
$T_{i}$ forms a partition of the zero divisor graph by $T_{a}=\\{x\in
ZD(\mathbb{Z}_{n})|gcf(x,n)=a\\}$. This concept was shown by Smith [3], where
the type graph was used to find all perfect $\Gamma(\mathbb{Z}_{n})$. Smith
used the notation $\Gamma^{T}(\mathbb{Z}_{n})$ to denote the type graph. In
that paper, four key observations were shown to be true regarding the type
graphs on $\mathbb{Z}_{n}$. In this section, we modify the definition of type
graph to fit the graph of
$\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}}$.
Additionally, we show these observations to be true over this type graph as
well. We then use analogues of some theorems from [3] to characterize the
perfectness of
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.

The following are two important theorems from [3].

######  Theorem 2.1 (Smith’s Main Theore).

[3] A graph $\Gamma(\mathbb{Z}_{n})$ is perfect iff $n$ is of one of the
following forms:

  1. 1.

$n=p^{a}$ for prime $p$ and positive integer $a$.

  2. 2.

$n=p^{a}q^{b}$ for distinct primes $p,q$ and positive integers $a,b$.

  3. 3.

$n=p^{a}qr$ for distinct primes $p,q,r$ and positive integer $a$.

  4. 4.

$n=pqrs$ for distinct primes $p,q,r,s$.

######  Theorem 2.2 (Simth’s Theorem 4.1).

[3] $\Gamma(\mathbb{Z}_{n})$ is perfect iff its type graph
$\Gamma^{T}(\mathbb{Z}_{n})$ is perfect.

######  Definition 2.3 (Type graph of
$\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}}$).

The type graph of
$\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}}$
denoted by
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
has a vertex set of the type classes $T(x_{1},x_{2},\cdots,x_{k})$ where
$(x_{1},x_{2},\cdots,x_{k})\neq(0,0,\cdots,0)$ nor $(1,1,\cdots,1)$, and
$x_{i}$ is a divisor of $n_{i}$, 1, or 0.
$T(x_{1},x_{2},\cdots,x_{k})=\\{(a_{1},a_{2},\cdots,a_{k})\mid|a_{i}\in\mathbb{Z}_{n_{i}}/0$
and $gcf(a_{i},n_{i})=x_{i}$ or $a_{i}=0$ if $x_{i}=0$ $\\}$. Arbitrary
$T(x_{1},x_{2},\cdots,x_{k})$ shares an edge with arbitrary
$T(y_{1},y_{2},\cdots,y_{k})$ iff $x_{i}y_{i}=0$ for all $i$.

Smith [3] gave the following four observations for the type graph of
$\Gamma(\mathbb{Z}_{n})$.

######  Theorem 2.4.

Each vertex of $\Gamma(\mathbb{Z}_{n})$ is in exactly one type class.

######  Theorem 2.5.

Arbitrary distinct vertices $T_{x}$ and $T_{y}$ share an edge in
$\Gamma^{T}(\mathbb{Z}_{n})$ iff each $a\in T_{x}$ shares an edge with each
$b\in T_{y}$ in $\Gamma(\mathbb{Z}_{n})$.

######  Theorem 2.6.

Arbitrary distinct vertices $T_{x}$ and $T_{y}$ don’t share an edge in
$\Gamma^{T}(\mathbb{Z}_{n})$ iff each $a\in T_{x}$ doesn’t share an edge with
each $b\in T_{y}$ in $\Gamma(\mathbb{Z}_{n})$.

######  Theorem 2.7.

In $\Gamma(\mathbb{Z}_{n})$ consider arbitrary $a$ and $b$ in the same type
class. An arbitrary vertex $c$ in $\Gamma(\mathbb{Z}_{n})$ shares an edge with
$b$ iff it shares an edge with $a$ also.

Following are the four analogues to the above results for
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.

######  Theorem 2.8.

Each vertex of
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
is in exactly one type class.

###### Proof.

Assume otherwise. Then there is a vertex $v$ that is not in any type class, or
$v$ is in multiple type classes.

  1. Case 1:

$v$ is not in any type class.

Then $v$ must have an element $a_{i}$ that is not 0 and whose gcf with $n_{i}$
is not a number $x_{i}$ which is clearly not true.

  2. Case 2:

$v$ is in multiple type classes.

Let $v=(a_{1},a_{2},\cdots,a_{k})\in T(x_{1},x_{2},\cdots,x_{k})\cap
T(y_{z},y_{2},\cdots,y_{k})$. Then for all $i\in\\{1,2,\cdots,k\\}$ if
$a_{i}=0$, then $x_{i}=y_{i}=0$ and if $a_{i}\neq 0$, then
$gcd(a_{i},n_{i})=x_{i}=y_{i}$ giving
$(x_{1},x_{2},\cdots,x_{k})=(y_{1},y_{2},\cdots,y_{k})$ which is a
contradiction.

∎

######  Theorem 2.9.

Arbitrary distinct vertices $T_{x}=T(x_{1},x_{2},\cdots,x_{k})$ and
$T_{y}=T(y_{1},y_{2},\cdots,y_{k})$ share an edge in
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
iff each $a\in T_{x}$ shares an edge with each $b\in T_{y}$ in
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.

###### Proof.

Let $T_{x}$ shares and edge with $T_{y}$. By the definition, $x_{i}y_{i}=0$
for every $i$. Consider arbitrary $(a_{1},\cdots,a_{i})\in T_{x}$ and
$(b_{1},\cdots,b_{i})\in T_{y}$.Since each $a_{i}$ is a multiple of $x_{i}$
and each $b_{i}$ is a multiple of $y_{i}$, $a_{i}b_{i}$ is a multiple of
$x_{i}y_{i}$ and therefore equal to 0. Then $(a_{1},\cdots,a_{i})$ and
$(b_{1},\cdots,b_{i})$ share an edge.
Conversely, let every $a\in T_{x}$ and $b\in T_{y}$ share an edge. Since
$x=(x_{1},x_{2},\cdots,x_{k})$ is an element of $T_{x}$, and
$y=(y_{1},y_{2},\cdots,y_{k})$ is an element of $T_{y}$, $x$ and $y$ share an
edge. Then $T_{x}$ must share an edge with $T_{y}$. ∎

######  Theorem 2.10.

Arbitrary distinct vertices $T_{x}=T(x_{1},x_{2},\cdots,x_{k})$ and
$T_{y}=T(y_{1},y_{2},\cdots,y_{k})$ don’t share an edge in
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
iff each $a\in T_{x}$ doesn’t share an edge with each $b\in T_{y}$ in
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.

###### Proof.

Let $T_{x}$ does not share an edge with $T_{y}$. By the definition,
$x_{i}y_{i}\neq 0$ for some $i$, which means $x_{i}y_{i}$ lacks some factor
$f$ of $n_{i}$. Consider arbitrary $(a_{1},\cdots,a_{i}\cdots,a_{k})\in T_{x}$
and $(b_{1},\cdots,b_{i},\cdots b_{k})\in T_{y}$. Now, $a_{i}$ is a multiple
of $x_{i}$ and $b_{i}$ is a multiple of $y_{i}$, and thus, $a_{i}b_{i}$ is a
multiple of $x_{i}y_{i}$. Since $gcf(a_{i},n_{i})=x_{i}$ and
$gcf(b_{i},n_{i})=y_{i}$, $a_{i}b_{i}$ also lacks the factor $f$ from $n_{i}$
and is therefore non-zero. So $(a_{1},\cdots,a_{k})$ and
$(b_{1},\cdots,b_{k})$ do not share an edge.
Conversely, let each $a\in T_{x}$ and $b\in T_{y}$ do not share an edge. Since
$x=(x_{1},x_{2},\cdots,x_{k})$ is an element of $T_{x}$, and
$y=(y_{1},y_{2},\cdots,y_{k})$ is an element of $T_{y}$, $x$ and $y$ don’t
share an edge. Then $T_{x}$ must not share an edge with $T_{y}$. ∎

######  Theorem 2.11.

In
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
consider arbitrary $a=(a_{1},a_{2},\cdots,a_{k})$ and
$b=(b_{1},b_{2},\cdots,b_{k})$ in the same type class
$T(t_{1},t_{2},\cdots,t_{k})$. An arbitrary vertex
$c=(c_{1},c_{2},\cdots,c_{k})$ shares an edge with $b$ iff it shares an edge
with $a$ also.

###### Proof.

Follows from Theorem 2.5 and 2.6. ∎

Next, we want have the following theorem:

######  Theorem 2.12.

$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
is perfect iff its type graph
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
is perfect.

To show this, we will use the following three theorems, whose proofs are
analogous to the corresponding proofs in [3].

######  Theorem 2.13.

Given arbitrary hole or antihole $H$ of length greater than $4$ in
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$,
every vertex in $H$ belongs to a different type class.

######  Theorem 2.14.

Let there be a hole or antihole $H$ length $l>4$ in
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.
Then the type graph
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
must also contain a hole or antihole length $l$.

######  Theorem 2.15.

Let there be a hole or antihole $H$ length $l>4$ in the type class
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.
Then the graph
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
must also contain a hole or antihole length $l$.

Using these theorems, now we can establish the following proof of Theorem
2.12.

###### Proof.

The proof is analogous to the proof in [3]. ∎

Now that we know perfectness in the type graph implies perfectness in the
zero-divisor graph, it is possible to find all such perfect
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.
As it turns out, for both $\Gamma^{T}(\mathbb{Z}_{n})$ and
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$,
we can exchange the primes of each $n_{i}$, and as long as the form of the
primes (the amount of primes and the power of each prime) stays the same, the
type graph will be isomorphic. To illustrate this, consider
$\Gamma^{T}(\mathbb{Z}_{p^{2}q}\times\mathbb{Z}_{p})$ where $p,q$ are prime.
This type graph is isomorphic to
$\Gamma^{T}(\mathbb{Z}_{r^{2}s}\times\mathbb{Z}_{t})$ where $r,s,t$ are prime,
even if the value of the primes change. We will use this to find all perfect
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.

######  Theorem 2.16.

Consider some $\Gamma^{T}(\mathbb{Z}_{n})$ and $\Gamma^{T}(\mathbb{Z}_{m})$
such that $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$
and $m=q_{1}^{\alpha_{1}}q_{2}^{\alpha_{2}}\cdots q_{k}^{\alpha_{k}}$. Then
$\Gamma^{T}(\mathbb{Z}_{n})\cong\Gamma^{T}(\mathbb{Z}_{m})$.

###### Proof.

Consider arbitrary vertex $u$ in $\Gamma^{T}(\mathbb{Z}_{n})$. $u$ is a factor
of $n$, so we can write $u=p_{1}^{x_{1}}p_{2}^{x_{2}}\cdots p_{k}^{x_{k}}$.
Note that $0\leq x_{i}\leq\alpha_{i}$, $\forall i$. Define a function
$f:\Gamma^{T}(\mathbb{Z}_{n})\to\Gamma^{T}(\mathbb{Z}_{m})$ as
$f(u)=f(p_{1}^{x_{1}}p_{2}^{x_{2}}\cdots
p_{k}^{x_{k}})=q_{1}^{x_{1}}q_{2}^{x_{2}}\cdots q_{k}^{x_{k}}$. Since $n$ and
$m$ both have the same amount of prime factors, and each corresponding prime
has the same power $\alpha_{i}$, the result follows.
∎

######  Theorem 2.17.

Consider $\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$
and $\Gamma^{T}(\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{k}})$ where
the prime factorization of $n_{i}$ has the same form as $m_{i}$ for each $i$.
That is, $n_{i}$ and $m_{i}$ have the same amount of prime factors and the
same power for each prime. Then
$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})\cong\Gamma^{T}(\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{k}})$.

###### Proof.

Take arbitrary $n_{i}$.
Denote the prime factorization of $n_{i}=p_{i,1}^{\alpha_{i,1}}\cdots
p_{i,j_{i}}^{\alpha{i,j_{i}}}$ where $j_{i}$ is the amount of prime of
$n_{i}$. Likewise, $m_{i}=q_{i,1}^{\alpha_{i,1}}\cdots
q_{i,j_{i}}^{\alpha{i,j_{i}}}$. Note that the only difference between these
factorizations are the value of the primes being used. The powers and amount
of primes are the same. Consider arbitrary
$(u_{1},\cdots,u_{k})\in\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$.
Each $u_{i}$ is a factor of $n_{i}$ or 0. We can write
$u_{i}=p_{i,1}^{x_{i,1}}\cdots p_{i,j_{i}}^{x_{i,j_{i}}}$ where $0\leq
x_{i,l}\leq\alpha_{i,l}$. Note that if $u_{i}$ is 1, each $x_{i,l}$ is 0 and
if $u_{i}$ is 0, $x_{i,l}=\alpha_{i,l}$ for every $l$.
Define a function
$f:\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})\to\Gamma^{T}(\mathbb{Z}_{m_{1}}\times\cdots\times\mathbb{Z}_{m_{k}})$
as $f(u_{1},\cdots,u_{k})=f(p_{1,1}^{x_{1,1}}\cdots
p_{1,j_{1}}^{x_{1,j_{1}}},\cdots,p_{k,1}^{x_{k,1}}\cdots
p_{k,j_{k}}^{x_{k,j_{k}}})$
$=(q_{1,1}^{x_{1,1}}\cdots
q_{1,j_{1}}^{x_{1,j_{1}}},\cdots,q_{k,1}^{x_{k,1}}\cdots
q_{k,j_{k}}^{x_{k,j_{k}}})=(v_{1},\cdots,v_{k})$. Note that all we did was
only replaced the primes. Hence the result follows as the previous one. ∎

######  Theorem 2.18.

$\Gamma^{T}(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ is
isomorphic to $\Gamma^{T}(\mathbb{Z}_{n_{1}\cdots n_{k}})$ if all $n_{i}$’s
are mutually co-prime.

###### Proof.

The proof follows by Chineese Remainder theorem. ∎

The next theorem will show how we can characterize perfectness of
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$. Because now
by the above three theorem without loss of generality we can simply choose
primes that will make each $n_{i}$ co-prime. Then we know the type graph will
be isomorphic to $\Gamma(\mathbb{Z}_{n})$ where $n$ is the product of all such
co-prime $n_{i}$. So $n$ will have a prime factorization with the total amount
of primes in all $n_{i}$ and they will have corresponding powers. So, we have
the following theorem.

######  Theorem 2.19.

$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\cdots\mathbb{Z}_{n_{k}})$
is perfect iff it is possible to find mutually co prime positive integers
$m_{1},m_{2}\cdots m_{k}$, so that each $m_{i}$ has same amount of prime
factors with same exponent in it’s prime factorization as that in $n_{i}$ and
$\Gamma(\mathbb{Z}_{m_{1}m_{2}\cdots m_{k}})$ is perfect.

######  Example 2.20.

For example, $\Gamma(\mathbb{Z}_{p^{2}q}\times\mathbb{Z}_{p})$ is perfect
because $\Gamma(\mathbb{Z}_{a^{2}bc})$ is perfect as shown by [3]. Also note,
no product with a dimension greater than four can be perfect.
$\Gamma(\mathbb{Z}_{p_{1}}\times\cdots\times\mathbb{Z}_{p_{5}})$ is not
perfect since no $\Gamma(\mathbb{Z}_{p_{1}\cdots p_{5}})$ is perfect as shown
by [3].

##  3\. Some properties of $\Gamma(\mathbb{Z}_{n})$

In this section we characterize $\Gamma(\mathbb{Z}_{n})$ by various qualities
such as completeness, cordiality and clique number. A helpful construction
used is the strong type graph. We define the strong type graph as the type
graph with self loops. We normally do not consider self-loops, in zero-divisor
graphs and type graphs, but in the strong type graph, a vertex has a loop at
it if it annihilates itself. We denote the strong type graph of
$\Gamma(\mathbb{Z}_{n})$ as $\Gamma^{S}(\mathbb{Z}_{n})$.
Another construction used commonly in this section is $n^{*}$. Consider some
$\Gamma(\mathbb{Z}_{n})$. Let $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots
p_{m}^{\alpha_{m}}$, then $n^{*}=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}\cdots
p_{m}^{\beta_{m}}$ where $\beta_{i}$ is half of $\alpha_{i}$ rounded up. This
construction is very useful, as some properties of vertices can be associated
with whether or not the vertex is a multiple of $n^{*}$.

######  Lemma 3.1.

Two arbitrary vertices $u$ and $v$ in $\Gamma(\mathbb{Z}_{n})$ that are both
in the same type class $T_{i}$ share an edge iff $T_{i}$ has a self-loop in
the strong type graph.

###### Proof.

Let $T_{i}$ have a self-loop. Then $i^{2}=0$. Since every $u,v\in T_{i}$ are
multiples of $i$, $u$ and $v$ will share an edge.
Conversely, let $T_{i}$ does not have a self-loop. Take arbitrary $u$ and $v$
in $T_{i}$. According to the definition of type class, $u$ and $v$ are some
multiple of $i$ where $gcf(u,n)=i$ and likewise for $v$. We can write $u=ai$
and $v=bi$ where $gcf(a,n/i)=1$ and $gcf(b,n/i)=1$. Assume $u$ and $v$ share
and edge. Then $uv=cn$, $abi^{2}=cn$ where $c$ is a natural number. So
$\frac{abi^{2}}{n}=c$. Since $T_{i}$ does not have a self-loop, $i^{2}\neq 0$
which means $n$ contains a factor not contained by $i^{2}$. Let this factor be
called $d$. Let $\frac{g}{d}$ represent the simplified form of the fraction
$\frac{i^{2}}{n}$ where $d$ is guaranteed to not be 1. By substitution,
$\frac{abg}{d}=c$. But this is a contradiction since $a$, $b$ and $g$ do not
share a factor with $n/i$, so cannot cancel the $d$ out of the denominator.
Therefore, the expression cannot be equal to $c$, a natural number. $u$ and
$v$ do not share and edge. ∎

######  Theorem 3.2.

$\Gamma(\mathbb{Z}_{p^{2}})$ is complete where $p$ is prime.

###### Proof.

Take arbitrary zero divisors of $\mathbb{Z}_{n}$, $u$ and $v$. $u$ and $v$
must both share a common factor with $n$, and the only possible factor is $p$
since $p^{2}$ is zero. So both $u$ and $v$ have a factor of $p$. Then $u$ and
$v$ share an edge. $\Gamma(\mathbb{Z}_{p^{2}})$ is complete. ∎

######  Theorem 3.3.

$\Gamma(\mathbb{Z}_{p^{x}})$ where $p$ is prime and $x\geq 3$ is not complete.

###### Proof.

Let $x\geq 3$.

  1. Case 1:

$p=2$: $p$ and $3p$ are distinct non-zero zero-divisors that are not
connected.

  2. Case 2:

$p\neq 2$: $p$ and $2p$ are distinct non-zero zero-divisors that are not
connected.

∎

######  Theorem 3.4.

$\Gamma(\mathbb{Z}_{n})$, where $n\geq 2$ is complete iff $n=p^{2}$.

###### Proof.

Let $\Gamma(\mathbb{Z}_{n})$ be complete. Assume two or more distinct prime
factors of $n$ exist. Label the smallest such factor by $p$. Now choose
another distinct prime factor of $n$ as $q$. $p$ is a zero divisor and shares
an edge with $n/p$. Since $p$ and $q$ are both prime factors of $n$, $pq\leq
n$. Also, since $p<q$, $p^{2}<pq$. So $p^{2}<pq\leq n$ which means $p^{2}$ is
non-zero and distinct from $p$. $p^{2}$ shares an edge with $n/p$ so $p^{2}$
is a distinct zero-divisor that does not share an edge with $p$, making
$\Gamma(\mathbb{Z}_{n})$ not complete. So $n$ must only have one prime factor.
Then, by Theorem 2.2, $\Gamma(\mathbb{Z}_{p^{x}})$ is not complete if $x\geq
3$. So $x=2$. So when $\Gamma(\mathbb{Z}_{n})$ is complete, $n=p^{2}$. The
converse follows by Theorem 3.2. ∎

######  Theorem 3.5.

$\Gamma(\mathbb{Z}_{n})$ is k-partite if $\Gamma^{S}(\mathbb{Z}_{n})$ is
k-partite.

###### Proof.

Let $\Gamma^{S}(\mathbb{Z}_{n})$ be k-partite. Then
$\Gamma^{S}(\mathbb{Z}_{n})$ can be partitioned into $k$ disjoint subsets
$S_{1},S_{2},\cdots,S_{k}$ such that no vertex in the same set share an edge.
Partition $\Gamma(\mathbb{Z}_{n})$ into a similar grouping
$Q_{1},Q_{2},\cdots,Q_{k}$ where $u\in Q_{i}$ iff $u\in T_{u}\in S_{i}$.
Consider arbitrary $u$ and $v$, vertices of $\Gamma(\mathbb{Z}_{n})$ that are
in the same partitioned set $Q_{i}$.

  1. Case 1:

$u$ and $v$ are in different type classes.
Call such classes $T_{u}$ and $T_{v}$. Then since $u$ and $v$ are both in
$Q_{i}$, $T_{u}$ and $T_{v}$ are both in $S_{i}$ which means $T_{u}$ does not
share an edge with $T_{v}$. So, by [3] $u$ and $v$ do not share an edge.

  2. Case 2:

$u$ and $v$ are in the same type class.
Call this class $T_{u}$. Then since $\Gamma^{S}(\mathbb{Z}_{n})$ is k-partite,
$T_{u}$ does not form a loop with itself. Hence, by Lemma 3.1, $u$ and $v$ do
not share an edge.

∎

######  Theorem 3.6.

$\Gamma(\mathbb{Z}_{n})$ is complete k-partite if $\Gamma^{S}(\mathbb{Z}_{n})$
is complete k-partite.

###### Proof.

Let $\Gamma^{S}(\mathbb{Z}_{n})$ be complete k-partite. Then by Theorem 2.4,
$\Gamma(\mathbb{Z}_{n})$ is k-partite. Using the partition used in Theorem
3.5, if we let $\Gamma^{S}(\mathbb{Z}_{n})$ be partitioned into $k$ disjoint
subsets $S_{1},S_{2},\cdots,S_{k}$, then $\Gamma(\mathbb{Z}_{n})$ can be
partitioned into $k$ disjoint subsets $Q_{1},Q_{2},\cdots,Q_{k}$, where
arbitrary vertex of $\Gamma(\mathbb{Z}_{n})$ is in $Q_{i}$ if its type class
is in $S_{i}$. Consider arbitrary vertices in $\Gamma(\mathbb{Z}_{n})$, $u$
and $v$, that are not in the same $Q_{i}$. Then $u$ and $v$ must be in
different type classes in two different $S_{i}$’s. Call these classes $T_{u}$
and $T_{v}$. Since $\Gamma^{S}(\mathbb{Z}_{n})$ is complete k-partite, $T_{u}$
and $T_{v}$ share an edge. Then $u$ and $v$ share an edge by [3]. ∎

######  Remark 3.7.

The converse of Theorem 3.5 and 3.6 is not always true. If the zero-divisor
graph is k-partite, but has a self-annihilating vertex, the strong type graph
will have a self-loop, which prevents it from being k-partite.

######  Theorem 3.8.

If $n$ is square free, $\Gamma(\mathbb{Z}_{n})$ is k-partite, where $k$ is the
number of distinct prime factors of $n$.

###### Proof.

Consider the strong type graph $\Gamma^{S}(\mathbb{Z}_{n})$. Let,
$n=p_{1}p_{2}\cdots p_{k}$. Partition the graph into $k$ sets
$S_{1},S_{2},\cdots,S_{k}$. A vertex $T_{a}$ in the strong type graph is in
$S_{i}$ if $gcf(a,p_{i})=1$ and $gcf(a,p_{h})>1$ for all $h<i$.
We now claim that $S_{1},S_{2},\cdots,S_{k}$ covers all the vertices of
$\Gamma^{S}(\mathbb{Z}_{n})$.
Assume there is a $T_{a}$ that is not in any $S_{i}$. Since $T_{a}$ is a
vertex, $a$ must be a factor of $n$ that is also less than $n$. So $a$ must
omit at least one $p_{i}$. So $gcf(a,p_{i})=1$. Since $T_{a}$ is not in any
$S_{i}$, there must exist some $h<i$ such that $gcf(a,p_{h})=1$. Choose the
smallest index $h$ of such $p_{h}$. Then $T_{a}$ must be in $S_{h}$ which is a
contradiction.
Our next claim is any two vertices $u$ and $v$ in the same partition do not
share an edge.
Consider arbitrary $u$ and $v$ in $S_{i}$. Both $u$ and $v$ do not contain
$p_{i}$ so they do not share an edge. So the strong type graph is k-partite.
By Theorem 3.5, $\Gamma(\mathbb{Z}_{p_{1}p_{2}\cdots p_{k}})$ is k-partite. ∎

######  Lemma 3.9.

Arbitrary type class $T_{a}$ in $\Gamma^{T}(\mathbb{Z}_{n})$ contains only one
element iff $a=\frac{n}{2}$.

###### Proof.

Let $T_{a}\in\Gamma(\mathbb{Z}_{n})$ have a type class that has only one
element. Assume $a\neq\frac{n}{2}$. Since $a$ is a factor of $n$,
$\frac{n}{a}=f$ is also a factor of $n$. Note that $f\geq 3$.
Consider the vertex $a(f-1)$. The quantity $(f-1)$ does not share any factors
with $f$. Since $af=n$, $gcf(a(f-1),n)=a$. So $a(f-1)\in T_{a}$. Also note
that $a<a(f-1)<n$. So $a(f-1)$ is a distinct vertex in $T_{a}$ which is a
contradiction. So $a=\frac{n}{2}$

Let $a=\frac{n}{2}$. Then a is the only element in $T_{a}$ since $2a=n$. ∎

######  Corollary 3.10.

Analogous to above, $T_{n/p}$ in $\Gamma^{T}(\mathbb{Z}_{n})$ contains exactly
$p-1$ elements if $p$ is the smallest prime factor of $n$.

######  Lemma 3.11.

There is at most one type class with only one element.

###### Proof.

Assume there are two or more distinct type classes that have only one element.
Call two of these classes $T_{u}$ and $T_{v}$. By Lemma 3.9, $u=v=\frac{n}{2}$
which is a contradiction. ∎

######  Theorem 3.12.

$\Gamma(\mathbb{Z}_{n})$ is k-partite if $\Gamma^{S}(\mathbb{Z}_{n})$ is
k-partite or $\Gamma^{T}(\mathbb{Z}_{n})$ is k-partite and the only self-
connected vertex of $\Gamma(\mathbb{Z}_{n})$ is $T_{\frac{n}{2}}$.

###### Proof.

Let $\Gamma^{S}(\mathbb{Z}_{n})$ be k-partite. By Theorem 3.5,
$\Gamma(\mathbb{Z}_{n})$ is k-partite. Let $\Gamma^{T}(\mathbb{Z}_{n})$ be
k-partite and let $\Gamma^{S}(\mathbb{Z}_{n})$ have only one self-connected
vertex, $T_{\frac{n}{2}}$. Consider arbitrary distinct $u$ and $v$, zero
divisors of $\Gamma(\mathbb{Z}_{n})$, that are in the same partition.

  1. Case 1:

$u$ and $v$ are in the same type class.
By Lemma 2.17, $T_{\frac{n}{2}}$ has only one element, so if $u$ and $v$ are
distinct, they cannot be in $T_{\frac{n}{2}}$. Then the type class they are in
are not self-connected so $u$ and $v$ do not share an edge.

  2. Case 2:

$u$ and $v$ are in different type classes.
Since $u$ and $v$ are in the same partition, their type classes are in the
same partition and do not share an edge. Thus, $u$ and $v$ do not share an
edge.

∎

######  Lemma 3.13.

A vertex in $\Gamma(\mathbb{Z}_{n})$ annihilates itself iff it is a multiple
of $n^{*}$.

######  Lemma 3.14.

Consider two arbitrary vertices in $\Gamma(\mathbb{Z}_{n})$ $u$ and $v$ such
that $u$ is a factor of $v$. The largest clique containing $v$, $M_{v}$ has a
magnitude greater than or equal to the $M_{u}$, the largest clique containing
$u$.

###### Proof.

Take arbitrary vertices $u$ and $v$ in $\Gamma(\mathbb{Z}_{n})$. Let $u$ be a
factor of $v$. Assume the opposite, that $M_{u}$ has a larger magnitude than
that of $M_{v}$. Every element $e$ in $M_{u}\setminus u$ has the property
$eu=0$. Then $\forall e\in M_{u}$, $ev=0$. So a clique $C$ exists with $v$ and
each $e$ in $M_{u}\setminus u$. $C$ has a magnitude equal to the magnitude of
$M_{u}$ which is a contradiction since $M_{v}$ is the largest clique
containing $v$. ∎

######  Theorem 3.15.

$cl(\Gamma(\mathbb{Z}_{n}))\geq\frac{n}{n^{*}}+k-1$ where $k$ is the number of
odd-power primes in the prime factorization of $n$.

###### Proof.

We claim that any two multiples of $n^{*}$ share an edge.
Take two arbitrary multiples of $n^{*}$, $an^{*}$ and $bn^{*}$. Since
$(n^{*})^{2}\geq n$ these two vertices will share an edge. So the multiples of
$n^{*}$ form a clique. Call it $C$. An arbitrary vertex of $C$ will be of the
form $an^{*}$ for $1<a<\frac{n}{n^{*}}$. The amount of elements in this clique
is $\frac{n}{n^{*}}-1$, so the clique number of the graph is at least
$\frac{n}{n^{*}}-1$. Now consider all vertices of the form $n^{*}/q$ where $q$
is an arbitrary odd-power prime in the prime factorization of $n$. Because
$n^{*}$ has a factor of $q$ with power of half rounded up, and $n^{*}/q$ has a
power of half rounded down, arbitrary $n^{*}/q$ shares an edge with each
$an^{*}$ in $C$. Also, each $n^{*}/q_{1}$ shares an edge to each other
$n^{*}/q_{2}$. This is because the power of $q_{1}$ in $n^{*}/q_{1}$ is half
rounded down and in $n^{*}/q_{2}$ it is half rounded up, and likewise for
$q_{2}$. Since $k$ is the number of distinct odd powered primes in the prime
factorization of $n$, $cl(\Gamma(\mathbb{Z}_{n}))\geq\frac{n}{n^{*}}+k-1$. ∎

######  Theorem 3.16.

$cl(\Gamma(\mathbb{Z}_{n}))\leq\frac{n}{n^{*}}+k-1$ where $k$ is the number of
odd-power primes in the prime factorization of $n$.

###### Proof.

Consider arbitrary clique $C$. Partition $C$ into sets $L$ and $N$ where $L$
is the set of vertices of $C$ that are not multiples of $n^{*}$ and $N$ is the
set of vertices of $C$ that are multiples of $n^{*}$. Consider arbitrary
vertex $l_{1}$ in $L$. Since $l_{1}$ is not a multiple of $n^{*}$, there must
be some prime factor $p_{1}$ of $n$ whose power in $l_{1}$ is less than half
of its power in $n$ (since if every prime factor was greater than or equal to
half, $l_{1}$ would be a multiple of $n^{*}$). Every other $l_{i}$ in $L$ must
have its $p_{1}$ factor with a power greater than or equal to half its power
in $n$ for it to share an edge with $l_{1}$. Consider another vertex $l_{2}$
in $L$. $l_{2}$ must also have a prime factor whose power is less than half
its power in $n$, but it cannot be $p_{1}$. Call it $p_{2}$. So each $l_{i}$
in $L$ must have a distinct prime factor $p_{i}$ that has a power less that or
equal to half its power in $n$. Let $m$ be the number of distinct prime
factors of $n$. Then there can be a maximum of $m$ many $l_{i}$ in $L$. $N$
has a maximum size of $\frac{n}{n^{*}}-1$, so the clique number is at most
$\frac{n}{n^{*}}+m-1$.
Consider some $e_{1}$, a vertex in $L$ whose corresponding $p_{1}$, has an
even power in $n$. $e_{1}$ does not share an edge with $n^{*}$. This means the
clique number is one less if $n$ has an even-powered prime. Consider another
$e_{2}$ that has an even $p_{2}$ whose power is less than half. Then $e_{2}$
does not share an edge with $p_{1}n^{*}$. In general, a vertex $e_{i}$ whose
corresponding $p_{i}$ has an even power does not share an edge with distinct
vertices $p_{1}p_{2}\cdots p_{i-1}n^{*}$. So the size of $C$ is reduced by the
number of even powered-primes of $n$. This value can be represented by $m-k$
where $k$ is the number of odd-powered primes of $n$. Hence, since $C$ is
arbitrary, $cl(\Gamma(\mathbb{Z}_{n}))\leq\frac{n}{n^{*}}+m-(m-k)-1$.
$cl(\Gamma(\mathbb{Z}_{n}))\leq\frac{n}{n^{*}}+k-1$. ∎

######  Theorem 3.17.

$cl(\Gamma(\mathbb{Z}_{n}))=\frac{n}{n^{*}}+k-1$.

###### Proof.

The proof follows by Theorem 3.15 and Theorem 3.16. ∎

######  Theorem 3.18.

There are no non-empty, non-complete, regular $\Gamma(\mathbb{Z}_{n})$.

###### Proof.

Consider all $\Gamma(\mathbb{Z}_{n})$ that are non-empty and not complete.
Assume $\exists$ some regular graph among these graphs.

  1. Case 1:

$n=p^{x}$ where $p$ is prime
If $x=1$, the graph is empty, and if $x=2$, the graph is complete, so $x\geq
3$. Then $p$ is a vertex that shares an edge with $p-1$ many other vertices,
and $p^{2}$ is a vertex that shares an edge with $p^{2}-1$ many other
vertices. Since the graph is regular, $p-1=p^{2}-1$, thus $p=p^{2}$, which
means $p=1$, a contradiction.

  2. Case 2:

$n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{m}^{\alpha_{m}}$, $m\geq 2$
and $p_{i}$ are all prime
Vertex $p_{1}$ shares an edge with $p_{1}-1$ many other vertices, and the
vertex $p_{2}$ shares an edge with $p_{2}-1$ many other vertices. Since the
graph is regular, $p_{1}-1=p_{2}-1$, thus $p_{1}=p_{2}$ which is a
contradiction since $p_{1}$ and $p_{2}$ are distinct.
So the only non-empty regular graphs are complete.

∎

######  Theorem 3.19.

$\Gamma(\mathbb{Z}_{n})$ is chordal iff $n=p^{x},2p$ or $2p^{2}$, where $p$ is
prime and $x$ is a positive integer.

###### Proof.

Let $n=p^{x}$. Assume that $\Gamma(\mathbb{Z}_{p^{x}})$ is not chordal. Then
$\exists$ a cycle $C$ of length $>$ 3, that has no chord. Let $y$ be a vertex
of $C$ that is not a multiple of $n^{*}$. Then, since the power of $p$ in $y$
has a power strictly less than $\frac{x}{2}$, each neighbor must be a multiple
of $n^{*}$. Then the two neighbors of $y$ in $C$ share an edge which is a
chord. So all vertices in $C$ must be a multiple of $n^{*}$ which also causes
a chord. So $\Gamma(\mathbb{Z}_{p^{x}})$ is chordal.

Let $n=2p$. $\Gamma(\mathbb{Z}_{2p})$ is a star because it is a line segment
only. Then, $\Gamma(\mathbb{Z}_{2p})$ is chordal.

Let $n=2p^{2}$. Assume $\Gamma(\mathbb{Z}_{2p^{2}})$ is non-chordal. Then
$\exists$ a cycle $C$ of length $>$ 3 that has no chord.
Let $a$ be a vertex of $C$ in the type class $T_{p}$. Each neighbor of $a$
must be a multiple of $2p$, and therefore, is in the type class $T_{2p}$. Each
multiple of $2p$ shares an edge, so there exists a chord in $C$. So there can
be no vertices in the type class $T_{p}$ in $C$.
Let $b$ be a vertex of $C$ that is in the type class $T_{2}$. Every neighbor
of $b$ must be in the type class $T_{p^{2}}$. But there is only one element in
$T_{p^{2}}$ so $b$ cannot have two distinct neighbors. So $b$ is not a vertex
of $C$.
So each vertex of $C$ must be in either $T_{p^{2}}$ or $T_{2p}$. Then since
there is only one element of $T_{p^{2}}$, and the magnitude of $C$ is at least
4, there are at least 3 elements of $T_{2p}$ in $C$. Those 3 elements form a
triangle since each multiple of $2p$ annihilates each other multiple of $2p$.
But $C$ can’t have a triangle since it is chord-less. This is a contradiction.

Let $n$ not be $p^{x}$, $2p$ or $2p^{2}$.

  1. Case 1:

$n=2^{x}p^{y}$ where $y\geq 3$, $x\geq 1$ and $p$ is an odd prime.
Then $2^{x}p-p^{y}-2^{x+1}p-p^{y-1}$ is a chord-less cycle.

  2. Case 2:

$n=2^{x}p^{y}$ where $x\geq 2$, $y\geq 1$ and $p$ is an odd prime.
Then $2p^{y}-2^{x}-p^{y}-2^{x+1}$ is a chord-less cycle.

  3. Case 3:

$n=p^{x}q^{y}$ where $p,q\geq 3$ where $p\neq q$ are primes and $x,y$ are non-
zero.
Then $p^{x}-q^{y}-2p^{x}-2q^{y}$ is a chord-less cycle.

  4. Case 4:

$n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ where $k\geq
3$ and $\alpha_{i}$ is non-zero.
Since $k\geq 3,n$ has an odd prime factor $p_{1}$. Then
$p_{1}^{\alpha_{1}}-n/p_{1}^{\alpha_{1}}-2p_{1}^{\alpha_{1}}-2n/p_{1}^{\alpha_{1}}$
is a chord-less cycle.
So $\Gamma(\mathbb{Z}_{n})$ is non-chordal if $n$ is not $p^{x}$, $2p$ or
$2p^{2}$.

∎

######  Lemma 3.20.

If $n^{*}\neq n$, $\Gamma(\mathbb{Z}_{n})$ has a simplicial vertex.

###### Proof.

Let $n^{*}\neq n$. Then $n/n^{*}$ is a vertex since $n/n^{*}$ shares an edge
with $n^{*}$ which is not a multiple of $n$. Since every neighbor of $n/n^{*}$
is a multiple of $n^{*}$ and every multiple of $n^{*}$ shares an edge,
$n/n^{*}$ is a simplicial vertex. So $\Gamma(\mathbb{Z}_{n})$ has a simplicial
vertex. ∎

Another construction $n_{*}$ can be useful. It is similar to $n^{*}$, but for
the odd powered primes, round down instead of up. Consider
$\Gamma(\mathbb{Z}_{n})$ where $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots
p_{k}^{\alpha_{k}}$. Define $n_{*}$ as
$n_{*}=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}\cdots p_{k}^{\beta_{k}}$ and
$\beta_{i}=\alpha_{i}/2$ if $\alpha_{i}$ is even and
$\beta_{i}=(\alpha_{i}-1)/2$ if $\alpha_{i}$ is odd.

Note that $n_{*}n^{*}=0$ and if $n$ is square-free, $n_{*}=1$.

######  Lemma 3.21.

Arbitrary vertex $v$ in $\Gamma(\mathbb{Z}_{n})$ is a simplicial vertex iff
$v\in T_{2}$ or $v\in T_{g}$ where $g$ is a factor of $n_{*}$.

###### Proof.

Take arbitrary $v$ in $\Gamma(\mathbb{Z}_{n})$. Let $v\in T_{2}$. Then $v$
only shares an edge with vertices in $T_{n/2}$. By Lemma 3.9, $T_{n/2}$ has
only one element, which makes a clique. So $v$ is simplicial.
Let $v\in T_{g}$ where $g$ is a factor of $n_{*}$. So $n_{*}=ag$ where $a$ is
a positive integer. Consider some vertex $h$ in $T_{j}$ that shares an edge
with $v$. Then $j*g=bn$ for positive integer $b$.
$\frac{jn_{*}}{a}=bn_{*}n^{*}$. $\frac{j}{a}=bn^{*}$. Then $j=abn^{*}$. So $j$
is a multiple of $n^{*}$ and therefore, $h$ is a multiple of $n^{*}$. Since
every multiple of $n^{*}$ shares an edge with every other such multiple, $v$
is a simplicial vertex.
Conversely, let $v$ be neither in $T_{2}$ nor in any $T_{g}$ where $g$ is a
factor of $n_{*}$. Then, since $v$ is not in any $T_{g}$, $v$ has some prime
with a power greater than half of that in $n$. Call that prime $p_{x}$ and its
power in $v$, $\alpha_{x}$. Let the type class of $v$ be called $T_{w}$.
Consider the type class $T_{n/w}$. Each vertex in $T_{n/w}$ shares an edge
with $v$. Since $v\notin T_{2}$, $T_{n/w}\neq T_{n/2}$. So by Lemma 3.9,
$T_{n/w}$ has more than one element. Since $n/w$ has a power of $p_{x}$ less
than that of half in $n$, none of the vertices in $T_{n/w}$ share an edge with
each other. So the neighbors of $v$ do not form a clique. Hence, $v$ is not
simplicial. ∎

######  Theorem 3.22.

$\Gamma(\mathbb{Z}_{n})$ has a simplicial vertex iff the prime factorization
of $n$ is not square free or $n$ is even.

###### Proof.

Let $n$ not be square free. Then, $n^{*}\neq n$. So by Lemma 3.20,
$\Gamma(\mathbb{Z}_{n})$ has a simplicial vertex.

Let $n$ be even. Then, 2 is a zero divisor. Every neighbor of 2 must be a
multiple of $n/2$ which there is only one of, so 2 is a simplicial vertex.

Let $n$ be square free and odd. 2 is therefore not a factor of $n$. Then
consider arbitrary vertex $x$. $x$ shares an edge with both $n/x$ and $2n/x$.
$2n/x$ is non-zero since $x$ is necessarily odd, and $n/x$ and $2n/x$ do not
share an edge since $n$ is odd. For if $\frac{n}{x}\frac{2n}{x}=ny$,
$2n=yx^{2}$ and $n=\frac{yx^{2}}{2}$ which is a contradiction. So there are no
simplicial vertices of $\Gamma(\mathbb{Z}_{n})$. ∎

Note: It follows by [3], (observation 3.2), if in $\Gamma(\mathbb{Z}_{n})$ a
vertex $u$ is simplicial then $T_{u}$ is simplicial in
$\Gamma^{T}(\mathbb{Z}_{n})$. But, not conversely. For example, in
$\Gamma^{T}(\mathbb{Z}_{12}),T_{3}$ is simplicial, where as $3$ is not so in
$\Gamma(\mathbb{Z}_{12})$.

######  Lemma 3.23.

If $\Gamma(\mathbb{Z}_{n})$ has three or more prime factors of $n$,
$\Gamma(\mathbb{Z}_{n})$ is not $\gamma-\beta$ perfect.

###### Proof.

Let $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ where
$k\geq 3$. By [2], the domination number is $k$. Construct some vertex map $V$
whose size is $k$.
We claim that $V$ must contain the vertex $n/p_{x}$ for every $p_{x}$ prime
factor of $n$.
Consider the vertex $n/p_{x}$ for some $p_{x}$ prime factor of $n$. Let
$n/p_{x}$ not be in $V$. Construct set $C=\\{p_{x}p_{i}|1\leq i\leq k\\}$.
$n/p_{x}$ shares an edge with every vertex in $C$. Since $n/p_{x}\notin V$,
every element of $C$ is in $V$. $C$ has $k$ many vertices, so $V$ has at least
$k$ many vertices. Consider vertex $p_{x}$. $p_{x}$ shares an edge with
$n/p_{x}$ which is not covered by $V$, so $V$ has at least $k+1$ vertices.
That is a contradiction since the size of $V$ is $k$. So each $n/p_{x}$ is in
$V$.

Consider the type classes $T_{n/p_{1}}$, $T_{n/p_{2}}$ and $T_{n/p_{3}}$. By
Lemma 3.11, there can be at most one type class with only one element. At
least two of these type classes have more than one element. Without loss of
generality, let them be $T_{n/p_{1}}$ and $T_{n/p_{2}}$. Since $n/p_{1}$ and
$n/p_{2}$ are both in $V$, choose different vertices in the type classes $u$
and $v$. $u$ and $v$ share an edge since they are multiples of $n/p_{1}$ and
$n/p_{2}$ respectively, so they share an edge, but are not in $V$. Then $V$
must contain at least one other element making the size of $V$ at least $k+1$.
This is a contradiction. We cannot construct a vertex map size $k$. So
$\Gamma(\mathbb{Z}_{n})$ is not $\gamma-\beta$ perfect. ∎

######  Theorem 3.24.

The only $\gamma-\beta$ perfect $\Gamma(\mathbb{Z}_{n})$ are
$n=2^{3},3^{2},p,2p$ and $3p$.

###### Proof.

Let $n=2^{3}$. The domination number clearly equals the smallest vertex map.

246

Let $n=3^{2}$. The domination number clearly equals the smallest vertex map.

36

Let $n=2p$. Then the graph is a star, so the domination number and the
smallest vertex map are both 1.
Let $n=3p$. Then $V=\\{p,2p\\}$ is both a minimal dominating set and a minimal
vertex map.
Let $n=p$. Then both the domination number and the smallest vertex map is 0
since the graph is empty.

Now, we will show that all other $\Gamma(\mathbb{Z}_{n})$ are not
$\gamma-\beta$ perfect.

Let $n=2^{2}$. The empty set is a vertex map since there are no edges in this
map, so smallest vertex map and the domination number are not the same.
Let $n=2^{x}$, $x\geq 4$. Then $2^{x-1}-2^{x-2}-3\cdot 2^{x-2}$ is a triangle.
Triangles prevent vertex maps of size 1, and by [2] the domination number is
1, so the values do not match.
Let $n=3^{x}$, $x\geq 3$. Then $3^{x-1}-2\cdot 3^{x-1}-3^{x-2}$ is a triangle
that prevents vertex maps of size 1.
Let $n=p^{x}$, $p\geq 5$, $x\geq 2$. Then $p^{x-1}-2\cdot p^{x-1}-3\cdot
p^{x-1}$ is a triangle.
Let $n=pq$, $q>p\geq 5$. The domination number is 2 by [2]. $p-q-2p-2q-3p-2q$
is a hole size 6. There cannot be a vertex map that covers a hole of that
size, so the smallest vertex map is not 2.
Let $n=p^{x}q$, $x\geq 2$. The domination number is 2.

  1. Case 1:

$p=2$.
Then $p^{x-1}q-p^{x}-q-p^{x+1}-pq$ is a non-induced sub-graph that cannot be
covered by a vertex map size 2.

  2. Case 2:

$p\neq 2$.
Then $p^{x}-p^{x-1}q-p-2p^{x-1}q-2p$ is a non-induced sub-graph that cannot be
covered by a vertex map size 2. The smallest vertex map is larger than 2
making the graph not $\gamma-\beta$ perfect.
Let $n=p^{x}q^{y}$, $x,y\geq 2$. The domination number is 2 by [2]. Assume
there is a vertex map $V$ size 2. Consider the edges $p-p^{x-}q^{y}$ and
$q-p^{x}q^{y-1}$. $V$ must contain at least vertex one of each edge. By Lemma
3.11 only one type class can have only one vertex. Consider the type classes
$T_{p^{x}q^{y-1}}$ and $T_{p^{x-1}q^{y}}$. At least one of them must contain
more than one vertex. Without loss of generality let that be
$T_{p^{x-1}q^{y}}$. Then there exists some $u\in T_{p^{x-1}q^{y}}$ that is not
in $V$. The edge $p-u$ is not covered by $V$, so the size of $V$ is at least
one more than 2 which is a contradiction.
Let $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$, $k\geq
3$. Then by Lemma 3.23, the graph is not $\gamma-\beta$ perfect.
So the only $\gamma-\beta$ graphs $\Gamma(\mathbb{Z}_{n})$ are
$2^{3},3^{2},p,2p$ and $3p$.

∎

##  4\. Some properties of
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$

In this section, we discuss some facts about
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$. It is often
possible to relate some properties of the individual
$\Gamma(\mathbb{Z}_{n_{i}})$ to the graph of the product. One example is that
the domination number of
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ has an upper
and lower bound corresponding to the domination number of each
$\Gamma(\mathbb{Z}_{n_{i}})$.

######  Theorem 4.1.

Consider two arbitrary commutative rings with unity, $R$ and $S$.
$\Gamma(R\times S)$ is complete iff $|R|=|S|=2$.

###### Proof.

Consider some $R$ and $S$ such that $|R|=|S|=2$. Since both $R$ and $S$ have
$1$, the only elements of $R$ and $S$ are $0$ and $1$, where by $1$ we denote
the unity of the respective ring . Then the zero divisor graph is
$(0,1)-(1,0)$ which is complete.
Conversely, let $R$ or $S$ have more than 2 elements. Without loss of
generality, let $R$ have more than 2 elements. Then $R$ has some element $a$
that is neither $1$ nor $0$. The graph $\Gamma(R\times S)$ has vertices
$(1,0)$ and $(a,0)$. These vertices do not share an edge because $1\cdot a=a$
which is not zero. So $\Gamma(R\times S)$ is not complete.
∎

######  Theorem 4.2.

$\Gamma(R_{1}\times\cdots\times R_{k})$ where $k\geq 2$ and each $R_{i}$ is a
commutative ring with $1$. This graph is complete iff $k=2$ and $|R_{i}|=2$
for all $i$.

###### Proof.

Consider some $\Gamma(R_{1}\times\cdots\times R_{k})$ where $k=2$ and all
$|R_{i}|=2$. Then by Theorem 3.0, $\Gamma(R_{1}\times\cdots\times R_{k})$ is
complete.
Consider some $\Gamma(R_{1}\times\cdots\times R_{k})$ that does not meet this
criteria. If $k\geq 3$, then $(1,0,1)$ and $(1,1,0)$ are two vertices that do
not share an edge. If any $|R_{i}|\geq 2$, then $R_{i}$ has an element $a$
that is not 0 or 1. Then $(\cdots,a,\cdots)$ does not share an edge with
$(\cdots,1,\cdots)$, where $a$ and $1$ are placed in the $i-th$ entry of the
respective elements. So $\Gamma(R_{1}\times\cdots\times R_{k})$ is not
complete. ∎

######  Theorem 4.3.

$\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$ where $n,m\geq 2$ is complete-
bipartite iff $n$ and $m$ are prime.

###### Proof.

Let $m$ and $n$ be prime. Then partition
$\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$ into sets $S_{n}$ and $S_{m}$
such that $S_{n}=\\{(x,0)|0<x<n\\}$ and $S_{m}=\\{(0,y)|0<y<m\\}$.
We claim that $S_{n}\cup S_{m}=\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$.
Assume, $\exists$ a zero divisor $a=(a_{1},a_{2})$ that is not in $S_{n}\cup
S_{m}$. Both $a_{1}$ and $a_{2}$ are non-zero as $m$ and $n$ are prime. Since
$a$ is a zero-divisor, there must be some $b=(b_{1},b_{2})$ that shares an
edge with $a$. So $a_{1}b_{1}=0$. Since $\mathbb{Z}_{n}$ has no non-zero
divisors, and $a_{1}$ is not zero, $b_{1}=0$. In the same way we find that
$b_{2}$ is zero. This means $a$ is not a zero-divisor because it only shares
an edge with 0. So $S_{n}\cup
S_{m}=\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$.
Take arbitrary $u,v\in S_{n}$. Then $u=(u_{1},0)$ and $v=(v_{1},0)$. Since
$u_{1}v_{1}\neq 0$, $uv\neq(0,0)$ which means $u$ and $v$ do not share an
edge. In the same way $u$ and $v$ do not share an edge if they are both in
$S_{m}$. So $u$ and $v$ do not share an edge if they are in the same partition
which is the definition of bipartite.
Thus, it follows from the construction of $S_{m}$ and $S_{m}$, that
$\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$ is complete bipartite.
Conversely, let $\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$ be complete
bipartite. Assume one or both n and m are not prime. Let the non-prime be $n$.
Then, there is a non-zero zero divisor of $\mathbb{Z}_{n}$. Call it $k$. Since
$\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$ is complete-bipartite, the
vertices of $\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$ can be partitioned
into 2 disjoint subsets such that no edges exist between two vertices in the
same partition, and every pair of vertices in different partitions share an
edge. $(1,0)$ is a zero divisor since it shares an edge with $(0,1)$. $(k,0)$
is also a zero divisor since it also shares an edge with $(0,1)$. Since
$(k,0)$ does not share an edge with $(1,0)$, they must be in the same
partition. Call it $S_{1}$ and let the other partition be $S_{2}$. Since $k$
is a zero-divisor of $\mathbb{Z}_{n}$, $\exists k^{\prime}$ not necessarily
distinct such that $k\cdot k^{\prime}=0$. Then $(k^{\prime},1)$ shares an edge
with $(k,0)$ which means $(k^{\prime},1)\in S_{2}$. Since
$\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$ is complete-bipartite, $(1,0)$
must share an edge with $(k^{\prime},1)$ since they are in opposite
partitions, but their product is not $0$, which is a contradiction. So both
$n$ and $m$ must be prime. ∎

######  Corollary 4.4.

From this theorem it follows that $\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$
has a complete bipartite sub-graph.

This is formed by $S_{n}\cup S_{m}$. If one of them is not a prime, we can
delete all vertices that has at least one an entry dividing either $n$ or $m$
respectively, to get a complete bipartite subgraph.

######  Theorem 4.5.

$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ where
$\forall n_{i}\geq 2$ and $k\geq 2$ is bipartite iff $k=2$ and both $n_{i}$
are prime, or one $n_{x}$ is prime and the other is $4$.

###### Proof.

Let $k=2$ and both $n_{1}$ and $n_{2}$ be prime. By Theorem 4.3,
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}})$ is bipartite.
Let $k=2$ and let one of $n_{i}$ be 4 and the other be prime. Without loss of
generality, let $n_{1}=4$. Then $n_{2}$ is prime. Partition the vertices into
set $A$ and $B$ where $A$ is the set of all vertices of the form $(a,0)$ where
$a\in\mathbb{Z}_{n_{1}}/0$ and $B$ is everything else. Consider arbitrary,
distinct elements of $A$, $(a_{1},0)$ and $(a_{2},0)$. They do not share an
edge, since there are no two distinct $a_{1}$ and $a_{2}$ that share an edge
in $\Gamma(\mathbb{Z}_{n_{1}})$. Consider all vertices in $B$. Assume $\exists
u,v\in B$ such that $u$ shares an edge with $v$. Then, $u=(u_{1},u_{2})$ and
$v=(v_{1},v_{2})$. Note that $u_{2}v_{2}\neq 0$. $u_{2}v_{2}=0$ which means
$u_{2}$ and $v_{2}$ are zero divisors in $\Gamma(\mathbb{Z}_{n_{2}})$. This is
impossible since there are no zero divisors in $\Gamma(\mathbb{Z}_{n_{2}})$.
So $\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ is
bipartite.
Conversely, let
$\Gamma(\mathbb{Z}_{n_{1}}\times\cdots\times\mathbb{Z}_{n_{k}})$ be bipartite.
We first claim that $k=2$.
Assume $k\geq 3$. Then, $(1,0,0,\cdots,0)-(0,1,0,\cdots,0)-(0,0,1,\cdots,0)$
is a triangle which cannot exist in a bipartite graph. So $k<3$. By our
definition, $k\geq 2$, so $k=2$
We now claim no $\Gamma(\mathbb{Z}_{n_{i}})$ can have two or more distinct
zero divisors.
Assume otherwise. Call two such divisors $u$ and $v$ that share an edge in
$\Gamma(\mathbb{Z}_{n_{i}})$. Without loss of generality, let $u$ and $v$ be
in the first slot (so $i=1$). Then $(u,0)-(v,0)-(0,1)$ is a triangle which
cannot exist in a bipartite graph. The only $\Gamma(\mathbb{Z}_{n_{i}})$ that
has one element is $\Gamma(\mathbb{Z}_{4})$. So all $n_{i}$ must be either 4
or prime.
Our final claim is it is not possible for both $n_{i}$ to be 4.
Assume otherwise. Then $(2,0)-(2,2)-(0,2)$ is a triangle which cannot exist in
a bipartite graph. So, because
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
is bipartite, $k=2$ and either both $n_{i}$ are prime, or one is 4 and the
other is prime. ∎

######  Theorem 4.6.

$\Gamma(R_{1}\times\cdots\times R_{k})$ where each $R_{i}$ is a commutative
ring with 1 is not perfect if some $\Gamma(R_{i})$ is not perfect.

###### Proof.

Let some $\Gamma(R_{i})$ be non-perfect. Then by the Strong Perfect Graph
theorem, there exists an odd hole or anti-hole $H$ of length 5 or greater. Let
$H$ have a length $l$. Then we write it as, $v_{1}-v_{2}-\cdots-
v_{l-1}-v_{l}-v_{1}$. Then a hole exists in $\Gamma(R_{1}\times\cdots\times
R_{k})$. Fill in the $i$th position with the vertices of $H$, and fill the
rest in with zeros. The hole is
$(0,\cdots,0,v_{1},0,\cdots,0)-(0,\cdots,0,v_{2},0,\cdots,0)-\cdots-(0,\cdots,0,v_{l-1},0,\cdots,0)-(0,\cdots,0,v_{l},0,\cdots,0)-(0,\cdots,0,v_{1},0,\cdots,0)$.
The same proof can be used for an anti-hole. So if any $\Gamma(R_{i})$ are
non-perfect, $\Gamma(R_{1}\times\cdots\times R_{k})$ will also be non-perfect.
∎

######  Note 4.7.

The converse of Theorem 3.4 is not true. In the graph
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2})$,
every $\Gamma(\mathbb{Z}_{2})$ is perfect, but we find the hole
$(1,1,0,0,0)-(0,0,1,1,0)-(1,0,0,0,1)-(0,1,1,0,0)-(0,0,0,1,1)$.

######  Theorem 4.8.

$\Gamma(R_{1}\times\cdots\times R_{x})$ where each $R_{i}$ is a commutative
ring with 1 is not regular if any $\Gamma(R_{i})$ is not empty.

###### Proof.

Take $\Gamma(R_{1}\times\cdots\times R_{x})$. Let some $\Gamma(R_{i})$ be non-
empty. Consider the vertex $g=(0,\cdots,0,1,0,\cdots,0)$ that has a 1 at the
$i^{th}$ index and 0 filled in all other indices. All neighbors of $g$ must be
of the form $(a_{1},a_{2},\cdots,a_{i-1},0,a_{i+1}\cdots,a_{x-1},a_{x})$, with
a zero at the $i^{th}$ index and any value in the other indices, not all zero.
Let there are $f$ many such vertices. Since $\Gamma(R_{i})$ is non-empty,
$\exists k\in\Gamma(R_{i})$. Since $k$ is a zero divisor, there must be some
$k^{\prime}\in\Gamma(R_{i})$, not necessarily distinct, such that $k\cdot
k^{\prime}=0$. Consider the vertex $h=(0,\cdots,0,k,0,\cdots,0)$ with $k$ in
the $i^{th}$ index and the rest filled in with 0. This vertex shares an edge
with all vertices that share an edge with $g$. So $h$ shares an edge with at
least $f$ vertices. But it also shares an edge with
$(1,\cdots,1,k^{\prime},1\cdots,1)$ which means $h$ shares an edge with at
least $f+1$ vertices. This means $g$ and $h$ have a different number of
neighbors, so $\Gamma(R_{1}\times\cdots\times R_{x})$ is not regular. ∎

######  Theorem 4.9.

For arbitrary rings $R$ and $S$, $cl(\Gamma(R\times S))\geq
cl(\Gamma(R))+cl(\Gamma(S))+|R^{\prime}||S^{\prime}|$ where $R^{\prime}$ and
$S^{\prime}$ are any set of self-annihilating vertices in a maximal clique of
$\Gamma(R)$ and $\Gamma(S)$.

###### Proof.

Let $C$ be a maximal clique in $\Gamma(R)$ and $D$ be a maximal clique in
$\Gamma(S)$. Construct an induced sub graph $X=\\{(c,0)or(0,d)|c\in C,d\in
D\\}$. Take two arbitrary, distinct vertices in $X$, call them $u$ and $v$.

  1. Case 1:

$u=(c_{1},0),v=(c_{2},0)$
Since $c_{1}$ shares an edge with $c_{2}$, $u$ and $v$ share an edge.

  2. Case 2:

$u=(0,d_{1}),v=(0,d_{2})$
since $d_{1}$ shares an edge with $d_{2}$, $u$ and $v$ share an edge.

  3. Case 3:

$u$ and $v$ are not of the same form.
Then, without loss of generality, let $u=(c,0)$ and $v=(0,d)$. $u$ shares an
edge with $v$.
So $X$ is a clique in $\Gamma(R\times S)$ with size
$cl(\Gamma(R))+cl(\Gamma(S))$.
Now consider $R^{\prime}$, the set of all self-annihilating vertices in $C$.
Each vertex in $R^{\prime}$ shares an edge with each other vertex in
$R^{\prime}$ because it is an induced sub-graph of a clique. It also shares an
edge with every vertex in $C$. Likewise, every vertex in $S^{\prime}$, the set
of all self-annihilating vertices in $D$, shares an edge with every other
vertex in $S^{\prime}$ and every vertex in $D$. Define the induced sub-graph
$Y=\\{(r,s)|r\in R^{\prime},s\in S^{\prime}\\}$. Every vertex $(r,s)\in Y$
shares an edge with every other vertex in $Y$ and every vertex in $X$, so
$X\cup Y$ forms a clique size
$cl(\Gamma(R))+cl(\Gamma(S))+|R^{\prime}||S^{\prime}|$.

∎

######  Corollary 4.10.

Consider $n$ many arbitrary rings $R_{1},R_{2},\cdots R_{n}$. Then,
$cl(\Gamma(R_{1}\times R_{2}\cdots
R_{n}))\geq\sum_{i=1}^{n}cl(\Gamma(R_{i}))+\sum_{i\neq j,i,j\in\\{1,2,\cdots
n\\}}|R_{i}^{\prime}||R_{j}^{\prime}|+\sum_{i\neq j\neq
k;i,j,k\in\\{1,2,\cdots
n\\}}|R_{i}^{\prime}||R_{j}^{\prime}||R_{k}^{\prime}|+\cdots+|R_{1}^{\prime}||R_{2}^{\prime}|\cdots|R_{k}^{\prime}|$,
where each $R_{i}^{\prime}$ is any set of self-annihilating vertices in a
maximal clique in $\Gamma(R_{i})$.

###### Proof.

Extending a similar type of construction in the proof of the above theorem, we
can consider $C_{1},C_{2},\cdots C_{n}$, a collection of maximal cliques in
$\Gamma(R_{1}),\Gamma(R_{2}),\cdots,\Gamma(R_{n})$ respectively. Construct an
induced sub graph $X_{i}=\\{(0,0,\cdots,c_{i},\cdots 0)|c_{i}\in
C_{i},\\},X=\bigcup_{i=1}^{n}{X_{i}}$, where we place the $c_{i}$ in the
$i-th$ coordinate. Then $X$ forms a click of cardinality
$\sum_{i=1}^{n}cl(\Gamma(R_{i}))$. Then consider,
$X_{ij}=\\{(0,0,\cdots,c_{i},\cdots c_{j}\cdots 0)|c_{i}\in
R^{\prime}_{i},c_{j}\in R^{\prime}_{j}\\}$, where
$R^{\prime}_{i},R^{\prime}_{j}$ are any set of self annihilating vertices in
maximal clique in $\Gamma(R_{i})$ and $\Gamma(R_{j})$, where we place the
$c_{i}$ and $c_{j}$ in the $i-th$ and $j-th$ entries respectively. Set
$Y=\bigcup_{i\neq j;i,j\in\\{1,2,\cdots n\\}}X_{ij}$. Then $Y$ forms a click
of cardinality $\sum_{i\neq j;i,j\in\\{1,2,\cdots
n\\}}|R_{i}^{\prime}||R_{j}^{\prime}|$, that is disjoint from $X$. In a
similar fashion we can construct $X_{ijk}$ for each distinct triplets
$i,j,k\in\\{1,2,\cdots n\\}$ and call their union $Z$ and $Z$ gives a click of
cardinality $\sum_{i\neq j\neq k;i,j,k\in\\{1,2,\cdots
n\\}}|R_{i}^{\prime}||R_{j}^{\prime}||R_{k}^{\prime}|$. Proceeding in this way
the result follows. ∎

######  Lemma 4.11.

Consider $\Gamma(\mathbb{Z}_{n})$ for arbitrary $n$. There is a maximal clique
$M$ that contains all self-annihilating vertices.

###### Proof.

Follows from Theorem 3.15 and Lemma 3.13. ∎

######  Theorem 4.12.

The clique number of $\Gamma(\mathbb{Z}_{n}\times\mathbb{Z}_{m})$ has a lower
bound of
$cl(\Gamma(\mathbb{Z}_{n})+cl(\Gamma(\mathbb{Z}_{m}))+(\frac{n}{n^{*}}-1)(\frac{m}{m^{*}}-1)$.

###### Proof.

Follows from Theorem 4.9 and the proof of Theorem 3.15 and Lemma 3.13. ∎

######  Theorem 4.13.

$\Gamma(R_{1}\times\cdots\times R_{k})$ where $k\geq 2$ and $R_{i}$ is a
commutative ring with 1 has a simplicial vertex iff some $\Gamma(R_{i})$ has a
simplicial vertex or some $|R_{i}|=2$.

###### Proof.

Take arbitrary $\Gamma(R_{1}\times\cdots\times R_{k})$. Let some
$\Gamma(R_{i})$ have a simplicial vertex $c$. Then consider the vertex
$(1,\cdots,1,c,1,\cdots,1)$ where $c$ is in the $i$th slot. Each neighbor of
$(1,\cdots,1,c,1,\cdots,1)$ must have 0 in every slot except the $i$th slot,
and the value of the $i$th slot must be a neighbor of $c$ in $\Gamma(R_{i})$.
Since each neighbor of $c$ shares an edge and each other slot is 0, all such
neighbors of $(1,\cdots,1,c,1,\cdots,1)$ form a clique. So
$\Gamma(R_{1}\times\cdots\times R_{k})$ has a simplicial vertex.

Let some $|R_{i}|=2$. Then $(1,\cdots,1,0,1,\cdots,1)$ only shares an edge
with $(0,\cdots,0,1,0,\cdots,0)$ making $(1,\cdots,1,0,1,\cdots,1)$
simplicial.

Let $\Gamma(R_{1}\times\cdots\times R_{k})$ have a simplicial vertex $v$.
Also, assume all $|R_{i}|>2$ and no $\Gamma(R_{i})$ have any simplicial
vertices. Consider arbitrary $v$ in $\Gamma(R_{1}\times\cdots\times R_{k})$.
Let $v$ have 0 at some index, $v=(\cdots,0,\cdots)$. Then since no
$|R_{i}|=2$, there exists some vertex $a\in R_{i}$ that is not 0 or 1. $v$
then shares an edge with $(0,\cdots,0,1,0,\cdots,0)$ and
$(0,\cdots,0,a,0,\cdots,0)$ which do not share an edge. So for $v$ to be
simplicial, it cannot contain any 0. Let $v$ have $a$ at some index, where $a$
is a zero divisor in its respective $\Gamma(R_{i})$. $v=(\cdots,a,\cdots)$.
Then $v$ shares an edge with every $(0,\cdots,0,a^{\prime},0,\cdots,0)$ where
$a\cdot a^{\prime}=0$ in $\Gamma(R_{i})$. $a$ is not simplicial since no
$\Gamma(R_{i})$ have any simplicial vertex, so some neighbor
$(0,\cdots,0,a^{\prime},0,\cdots,0)$ will not share an edge with another
neighbor of the same form. So $v$ is not simplicial if it has any zero-
divisors in its slots. For $v$ to be simplicial, every slot must be a non-
zero, non-zero-divisor. However, elements of that form are not vertices. So
$\Gamma(R_{1}\times\cdots\times R_{k})$ has no simplicial vertices, which is a
contradiction. The assumption that all $|R_{i}|>2$ and no $\Gamma(R_{i})$ have
any simplicial vertices is false. So some $|R_{i}|>2$ or some $\Gamma(R_{i})$
has a simplicial vertex. ∎

######  Theorem 4.14.

$\Gamma(R_{1}\times\cdots\times R_{k})$ where $R_{i}$ is a commutative ring
with 1 is non-chordal if any $\Gamma(R_{i})$ is non-chordal.

###### Proof.

Consider arbitrary $\Gamma(R_{1}\times\cdots\times R_{k})$. Then let some
$\Gamma(R_{i})$ be non-chordal. So there exists a cycle $a_{1}-a_{2}-\cdots-
a_{k}-a_{1}$ greater than 3 with no chords. Then in
$\Gamma(R_{1}\times\cdots\times R_{k})$, there is a cycle
$(0,..,a_{1},\cdots,0)-(0,\cdots,a_{2},\cdots,0)-\cdots-(0,\cdots,a_{k},\cdots,0)-(0,\cdots,a_{1},\cdots,0)$,
which makes it non-chordal. ∎

######  Lemma 4.15.

$\Gamma(R_{1}\times\cdots\times R_{k})$ where $R_{i}$ is a commutative ring
with 1 and $k\geq 2$ is non-chordal if more than one $|R_{i}|\geq 3$.

###### Proof.

In $\Gamma(R_{1}\times\cdots\times R_{k})$, let two or more $|R_{i}|\geq 3$.
Without loss of generality, let the first two slots be the $R_{i}$ with a
magnitude greater than or equal to 3. Then
$(1,0,\cdots,0)-(0,1,\cdots,0)-(a,0,\cdots,0)-(0,b,\cdots,0)$ where $a$ is a
non-trivial element of $R_{1}$ and $b$ is a non-trivial element of $R_{2}$, is
a cycle with no chord. So $\Gamma(R_{1}\times\cdots\times R_{k})$ is non-
chordal. ∎

######  Lemma 4.16.

$\Gamma(R_{1}\times\cdots\times R_{k})$ where $R_{i}$ is a commutative ring
with 1 is non-chordal if $k\geq 4$.

###### Proof.

Let $k>4$. Then
$(1,1,0,0,\cdots,0)-(0,0,1,1,\cdots,0)-(1,0,0,0,\cdots,0)-(0,0,0,1,\cdots,0)$
is a chord-less cycle. So $\Gamma(R_{1}\times\cdots\times R_{k})$ is non-
chordal. ∎

######  Lemma 4.17.

$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\mathbb{Z}_{n_{3}})$
where at least one $n_{i}>2$ is non-chordal.

###### Proof.

Without loss of generality, let $n_{3}>2$. Then,
$(1,0,0)-(0,0,2)-(1,1,0)-(0,0,1)$ is a chord-less cycle. ∎

######  Theorem 4.18.

The only chordal
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
where $n_{i}\geq 2$ and $k\geq 2$ are
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p})$,
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p^{2}})$ and
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2})$.

###### Proof.

Consider $\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p})$. Since
$\Gamma(\mathbb{Z}_{p})$ has no vertices, the only vertices of
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p})$ are $(1,0)$ or of the form
$(0,x)$ where $0<x<p$. So the graph is a star making it chordal.

Consider $\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p^{2}})$. Assume that
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p^{2}})$ is non-chordal. Then there
exists a cycle $C$ length greater than $3$ that has no chord. Let $v$ be an
arbitrary vertex in $C$.
Let $v$ have a multiple of $p$ as its second element, $v=(a,bp)$. Then every
vertex that is not a neighbor of $v$ in $C$ must have a non-zero non-multiple
of $p$ as its second element. Therefore, both neighbors of $v$ must have 0 as
their second element so that they share an edge with their other neighbor. So
both neighbors of $v$ are $(1,0)$. We cannot repeat vertices so $v$ cannot
have a multiple of $p$ as its second element. That means the only possible
vertices in $C$ are $(1,0)$ and $(0,b)$ where $b$ is a non-zero non-multiple
of $p$. A cycle of size $4$ or greater cannot be constructed out of these
vertices since we cannot write $(1,0)$ twice and $(0,b)$ does not share an
edge with itself. $C$ cannot be constructed, so
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p^{2}})$ is chordal.

Consider $\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2})$. The
graph of $\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2})$ is
shown below and is chordal.

(1, 0, 1)(0, 1, 0)(0, 0, 1)(1, 0, 0)(0, 1, 1)(1, 1, 0)

To prove the converse, let’s assume the opposite. Let there be a chordal
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
not listed. By Lemma 4.15, only one $n_{i}$ can be greater than 2. By Lemma
4.16, $k\leq 3$. By Theorem 4.14, if any $n_{i}$ are non-chordal,
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
will be non-chordal. So every $n_{i}$ must be $p^{x}$, $2p$, or $2p^{2}$ which
was shown by Theorem 4.17.

So the only possible
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$
are $\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p^{x}})$,
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2p})$,
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2p^{2}})$,
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{p^{x}})$,
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2p})$ and
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2p^{2}})$.

In $\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{p^{x}})$ where $x\geq 3$ and $p$ is
prime, $(1,p^{x-1})-(0,(p-1)p)-(1,0)-(0,p)$ is a chord-less cycle.

In $\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2p})$ where $p\geq 3$ is a prime,
$(1,0)-(0,4)-(1,p)-(0,2)$ is a chord-less cycle.

In $\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2p^{2}})$ where $p\geq 3$ is a
prime, $(1,2p)-(0,p)-(1,4p)-(0,p^{2})$ is a chord-less cycle.

By Lemma 3.15,
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{p^{x}})$,
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2p})$ and
$\Gamma(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2p^{2}})$ are all
non-chordal where $p\geq 3$.

So there are no other chordal
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.
∎

######  Lemma 4.19.

$D(\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}}))$
has an upper bound of
$2[D(\Gamma(\mathbb{Z}_{n_{1}}))+D(\Gamma(\mathbb{Z}_{n_{2}}))+\cdots+D(\Gamma(\mathbb{Z}_{n_{k}}))]$.

###### Proof.

Let $d_{i}$ be the domination number of $\Gamma(\mathbb{Z}_{n_{i}})$. Then
each $\Gamma(\mathbb{Z}_{n_{i}})$ has a dominating set $D_{i}$ size $d_{i}$
Then consider the sets
$A_{i}=\\{(0,\cdots,0,v,0,\cdots,0)\mid|v\in D_{i}\\}$ where the $i$-th slot
is filled with arbitrary vertex in $D_{i}$ and the rest are 0. Also consider
$B_{i}$, the set of neighbors of each vertex in $A_{i}$, with only one
neighbor for each vertex. Now consider $\cup_{i=1}^{k}(A_{i}\cup B_{i})$ and
arbitrary vertex
$v\in\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.

  1. Case 1:

$v$ has an element $e$ in some $i$th slot that is a vertex of
$\Gamma(\mathbb{Z}_{n_{i}})$.
If $e\in D_{i}$, then $v$ shares an edge with the corresponding vertex in
$B_{i}$, and if $e\notin D_{i}$, then $v$ shares an edge with some vertex in
$D_{i}$.

  2. Case 2:

$v$ has 0 in some $i$th slot.

Then $v$ shares an edge with some vertex in $A_{i}$.
So if neither of these cases is true, none of the elements of $v$ can be zero
or a vertex in its corresponding $\Gamma(\mathbb{Z}_{n_{i}})$, so the only
neighbor of $v$ is $(0,..,0)$ which means $v$ is not a vertex. Then
$\cup_{i=1}^{k}(A_{i}\cup B_{i})$ is a dominating set. $A_{i}$ and $B_{i}$
both have size $D(\Gamma(\mathbb{Z}_{n_{i}}))$ since it only has one vertex
for each vertex in its corresponding $D_{i}$. So the size of
$\cup_{i=1}^{k}(A_{i}\cup B_{i})$ is
$2(D(\Gamma(\mathbb{Z}_{n_{1}}))+D(\Gamma(\mathbb{Z}_{n_{2}}))+\cdots+D(\Gamma(\mathbb{Z}_{n_{k}})))$
which is an upper bound of the domination number.

∎

######  Lemma 4.20.

$D(\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}}))$
has a lower bound of
$D(\Gamma(\mathbb{Z}_{n_{1}}))+D(\Gamma(\mathbb{Z}_{n_{2}}))\\\
+\cdots+D(\Gamma(\mathbb{Z}_{n_{k}}))$.

###### Proof.

Let $D$ be an arbitrary dominating set of
$\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}})$.
Consider the vertex $v=(1,\cdots,1,a,1,\cdots,1)$ where $a$ in the $i$th slot
is a vertex of $\Gamma(\mathbb{Z}_{n_{i}})$. The only possible neighbors of
$v$ are of the form $(0,\cdots,0,b,0,\cdots,0)$ where $b$ is a neighbor of $a$
in $\Gamma(\mathbb{Z}_{n_{i}})$. Construct a subset $A_{i}$ that is all
vertices in $D$ of the form $(0,..,0,b,0,\cdots,0)$ or
$(1,\cdots,1,b,1,\cdots,1)$ where $b$ is a vertex in
$\Gamma(\mathbb{Z}_{n_{i}})$.
We claim that arbitrary $A_{i}$ has a size of at least $d_{i}$, where $d_{i}$
is the domination number of $\Gamma(\mathbb{Z}_{n_{i}})$.
Assume otherwise. Then there are less than $d_{i}$ vertices of the form
$(0,\cdots,0,b,0,\cdots,0)$ and $(1,\cdots,1,b,1,\cdots,1)$. Take some $a$ in
$\Gamma(\mathbb{Z}_{n_{i}})$. Since some vertex in $D$ shares an edge with
every vertex not in $D$, arbitrary $v=(1,\cdots,1,a,1,\cdots,1)$ either shares
an edge with some $(0,\cdots,0,b,0,\cdots,0)$ or is itself in $D$ and
therefore in $A_{i}$. If $v$ is not in $D$, then $v$ shares an edge with some
$(0,\cdots,0,b,0,\cdots,0)$ which means $a$ shares an edge with some $b$ in
$\Gamma(\mathbb{Z}_{n_{i}})$. If $v$ is in $D$, then
$(1,\cdots,1,a,1,\cdots,1)$ is in $A_{i}$. Construct a set $H$ that contains
all $a$ in the $i$th slot of all such $v$. $H$ forms a dominating set of
$\Gamma(\mathbb{Z}_{n_{i}})$ size less than $d_{i}$ which is a contradiction
since $D(\Gamma(\mathbb{Z}_{n_{i}})=d_{i}$. So $A_{i}$ has a size of at least
$d_{i}$.
Next, each $A_{i}$ is disjoint from each other since $b$ in the $i$th slot can
never be 0 or 1, which means there will be no duplicate vertices. So the sum
of the sizes of each $A_{i}\subseteq D$ will be greater than or equal to the
sum of the domination number of each $\Gamma(\mathbb{Z}_{n_{i}})$. This is a
lower bound of the domination number. ∎

Combining Lemma 4.19 and 4.20 we get the following.

######  Theorem 4.21.

$D(\Gamma(\mathbb{Z}_{n_{1}}))+D(\Gamma(\mathbb{Z}_{n_{2}}))+\cdots+D(\Gamma(\mathbb{Z}_{n_{k}}))$
$\leq$
$D(\Gamma(\mathbb{Z}_{n_{1}}\times\mathbb{Z}_{n_{2}}\times\cdots\times\mathbb{Z}_{n_{k}}))$
$\leq$
$2[D(\Gamma(\mathbb{Z}_{n_{1}}))+D(\Gamma(\mathbb{Z}_{n_{2}}))+\cdots+D(\Gamma(\mathbb{Z}_{n_{k}}))]$.

The next theorem talks about the coefficients of a Domination Polynomial.

######  Theorem 4.22.

In arbitrary $\Gamma(\mathbb{Z}_{p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots
p_{k}^{\alpha_{k}}})$, $k\geq 3$, and each $p_{i}$ is a distinct prime number,
the coefficient $c$ of the smallest degree of the domination polynomial is
$(p_{1}-1)(p_{2}-1)\cdots(p_{k}-1)$.

###### Proof.

Consider $\Gamma(\mathbb{Z}_{p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots
p_{k}^{\alpha_{k}}})$, $k\geq 3$. Let
$n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$. Construct
set $D$ that has exactly one element from each type class $T_{n/p_{i}}$. Since
every vertex of $\Gamma(\mathbb{Z}_{p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots
p_{k}^{\alpha_{k}}})$ must be a multiple of some $p_{i}$, every vertex shares
an edge with some vertex in some $T_{n/p_{i}}$ and therefore, $D$. So $D$ is a
dominating set.
We claim that for arbitrary minimal dominating set $D$, exactly one vertex
must be present from each type class $T_{n/p_{i}}$.
Assume the opposite. Then there exists a dominating set $D$ that either
doesn’t have a vertex from some type class $T_{n/p_{x}}$ or has an extra
vertex not in any type class $T_{n/p_{x}}$. Let $D$ not have any vertices from
$T_{n/p_{x}}$. Since the only neighbors of vertices in $T_{p_{x}}$ are in
$T_{n/p_{x}}$, every vertex in $T_{p_{x}}$ must be in $D$. $p_{x}\neq n/2$
because otherwise $2p_{x}=n$,
$2p_{x}=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ and
$2=\frac{p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots
p_{k}^{\alpha_{k}}}{p_{x}}$ which is not possible. So by Lemma 1.10,
$T_{p_{x}}$ has more than one element. If $D$ contains at least one vertex
from all $T_{n/p_{x}}$ except $T_{p_{x}}$, then the size of $D$ is larger than
$A$ above. So $D$ is not a minimal dominating set. If $D$ lacks any vertices
from other $T_{n/p_{i}}$, then for each vertex missing, two or more must be
added from $T_{p_{x}}$. In which case $D$ would also not be minimal. So $D$
must contain at least one vertex from each $T_{n/p_{i}}$. There also cannot be
any additional vertices, either from type classes not of the form
$T_{n/p_{x}}$, nor multiple from the same type class. Otherwise $D$ would not
be minimal.
Since there are $p_{i}-1$ vertices in $T_{n/p_{i}}$, the total amount of
possible minimal dominating sets $D$ is $(p_{1}-1)(p_{2}-1)\cdots(p_{k}-1)$. ∎

######  Theorem 4.23.

$\Gamma(\mathbb{Z}_{p_{1}}\times\mathbb{Z}_{p_{2}}\times\cdots\times\mathbb{Z}_{p_{k}})$
is k-partite where every $p_{i}$ is prime.

###### Proof.

Consider some graph
$\Gamma(\mathbb{Z}_{p_{1}}\times\mathbb{Z}_{p_{2}}\times\cdots\times\mathbb{Z}_{p_{k}})$.
Construct a collection of subsets $S_{i}$ which is the set of all vertices
with a non-zero term in the $i$th slot and zero in any slot less than $i$.
$S_{1}=\\{(a,\cdots.)|a\in\mathbb{Z}_{p_{1}},a\neq 0\\}$
$S_{2}=\\{(0,a,\cdots)|a\in\mathbb{Z}_{p_{2}},a\neq 0\\}$
$\cdots$
$S_{k}=\\{(0,0,\cdots,0,a)|a\in\mathbb{Z}_{p_{k}},a\neq 0\\}$
We claim that no two vertices $u,v$ from the same subset $S_{x}$ share an
edge.
Consider arbitrary vertices $u$ and $v$ in some $S_{x}$. By the definition,
the $x$th slot of $u$ and $v$ has a non-zero term from $\mathbb{Z}_{p_{x}}$.
Since $\mathbb{Z}_{p_{x}}$ has no non-zero, zero divisors, the terms in the
$x$th slot will not multiply to get 0, so $u$ and $v$ do not share an edge.
No we claim that all the $S_{i}$ form a partition of
$\Gamma(\mathbb{Z}_{p_{1}}\times\mathbb{Z}_{p_{2}}\times\cdots\times\mathbb{Z}_{p_{k}})$.
Assume there is a vertex $v$ not in any $S_{i}$. Let $v$ have a non-zero
element $a$ in the $x$th slot. The by definition it is in $S_{x}$, or in some
$S_{i}$, $i<x$ if some $i$th slot also has a non-zero element. So $v$ cannot
have any non-zero elements and thus, $v=0$ which is not a vertex. $\cup S_{i}$
is the vertex set of
$\Gamma(\mathbb{Z}_{p_{1}}\times\mathbb{Z}_{p_{2}}\times\cdots\times\mathbb{Z}_{p_{k}})$.
Assume there is a $v$ in multiple $S_{i}$, say $S_{x}$ and $S_{y}$. Without
loss of generality, let $x<y$. Then the $x$th slot of $v$ has a non-zero term
$a$ because it is in $S_{x}$. But the $x$th slot must be zero because $v$ is
in $S_{y}$. That is a contradiction, so there are no overlaps in the
partition.
$S_{i}$ is a k-partite partition, so
$\Gamma(\mathbb{Z}_{p_{1}}\times\mathbb{Z}_{p_{2}}\times\cdots\times\mathbb{Z}_{p_{k}})$
is k-partite. ∎

##  5\. Zero divisor graph of the poset $D_{n}$

Zero divisor graph of a poset has been studied in [8], [9], [10]. We always
have Clique number of the zero divisor graph of a ring does not exceed the
Chromatic number of that. Beck conjectured that that for an arbitrary ring
$R$, they are same. But Anderson and Naseer [6] have shown that this is not
the case in general, namely they presented an example of a commutative local
ring $R$ with $32$ elements for which Chromatic number is strictly bigger than
the clique number.In [6] Nimbhorkar, Wasadikar and DeMeyer have shown that
Beck’s conjecture holds for meet-semilattices with $0$, i.e., commutative
semigroups with $0$ in which each element is idempotent. Infact, it is valid
for a much wider class of relational structures, namely for partially ordered
sets (posets, briefly) with $0$. Now, to any poset $(P,\leq)$, with a least
element $0$ we can assign the graph $G$ as follows: its vertices are the
nonzero zero divisors of $P$, where a nonzero $x\in P$ is a called a zero
divisor if there exists a non zero $y\in P$, so that $L(x,y)=0,L(x,y)=\\{z\in
P|z\leq x,y\\}$. And $x,y$ are connected by an edge if $L(x,y)=0$. We discuss
here some properties of the zero divisor graph of a specific poset $D_{n}$.
Very often we used the prime factorization of the positive integer $n$. By
abuse of notation, let us call $D_{n}$ as the zero divisor graph of the poset
$D_{n}$. Note that, the vertex set of $D_{n}$ is the set of all factors of $n$
that are not divisible by some prime factor of $n$. Also, note that, two
vertices in $D_{n}$ are connected by an edge if and only if they are mutually
co-prime.

######  Remark 5.1 (Properties of $D_{n}$).

  1. i.

If $n=p^{m}$ for some prime $p$ and positive integer $m$, then $D_{n}$ is
trivial.

So from now on consider $D_{n}$ where $n\neq p^{m}$ where $p$ and $m$ are as
mentioned.

  2. ii.

The diameter of $D_{n}$ is 3 iff $n$ has three distinct prime factors namely
$p$, $q$, $r$. This is shown by the path $pq-r-p-qr$. Otherwise, the diameter
is 1 or 2, as $D_{p^{m}q^{n}}$ is complete bipartite which has diameter 2 or
in the case of $m=n=1$ has diameter 1. [7] shows zero divisors of a poset have
diameter of 1, 2, or 3.

  3. iii.

$D_{n}$ is complete only when $n=pq$, where $p$ and $q$ are two distinct
primes. $D_{n}$ is complete bipartite iff $n=p^{m}q^{s}$ where $m$ and $s$ are
two positive integers.

  4. iv.

We have the clique number of $D_{n}$ and a few coefficients of the clique
polynomial.The clique number of $D_{n}$ is the number of distinct prime
factors of $n$. If
$n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}p_{3}^{\alpha_{3}}\cdots
p_{r}^{\alpha_{r}}$ where $p_{i}$’s are distinct primes $\forall i$, any set
of vertices $\\{p_{1}^{\beta_{1}},p_{2}^{\beta_{2}},p_{3}^{\beta_{3}}\cdots
p_{r}^{\beta_{r}}\\}$, where $1\leq\beta_{i}\leq\alpha_{i}$ $\forall i$ forms
a maximal clique. This is a clique because no two vertices in a clique can
have a common prime factor. Also, if any vertex of a clique has more than one
prime factor, the clique will not be maximal. Hence the clique number is $r$,
the number of distinct primes of $n$. And the leading coefficient in the
clique polynomial is $\alpha_{1}\alpha_{2}\cdots\alpha_{r}$. The coefficient
of $x^{r-1}$ is
$\sum_{i=1}^{r}(\alpha_{1}\alpha_{2}\cdots\alpha_{i-1}\alpha_{i+1}\cdots\alpha_{r})+\binom{r}{2}\alpha_{1}\alpha_{2}\cdots\alpha_{r}.$
Reason: Consider a clique of size $r-1$. If all the vertices has single prime
factors then, there are
$\sum_{i=1}^{r}(\alpha_{1}\alpha_{2}\cdots\alpha_{i-1}\alpha_{i+1}\cdots\alpha_{r})$
many of this type, as a typical clique of this type is a set of the form
$\\{p_{1}^{\beta_{1}},p_{2}^{\beta_{2}},\cdots
p_{i-1}^{\beta_{i-1}},p_{i+1}^{\beta_{i+1}},\cdots p_{r}^{\beta_{r}}\\}$,
where $1\leq\beta_{j}\leq\alpha_{j}\forall j\in\\{1,2,\cdots r\\}$. Otherwise,
exactly one vertex will contain two primes. And in that case we will obtain
$\binom{r}{2}\alpha_{1}\alpha_{2}\cdots\alpha_{r}$ many such clique sets with
cardinality $r-1$. No element in a clique set can have three distinct primes
in it’s prime factorization. Hence the result follows.

  5. v.

The domination number of $D_{n}$ is the number of distinct prime factors of
$n$, same as the clique number, as any dominating set must not omit a prime
factor of $n$. If some $p_{i}$ is missing from a set of vertices $V$, then the
vertex $p_{1}p_{2}\cdots p_{i-1}p_{i+1}\cdots p_{r}$ is not adjacent to any
vertex in $V$. Furthermore, if we let $V$ be the set of all distinct primes of
$n$, each vertex in $D_{n}$ must share an edge with at least one vertex in $V$
because each vertex in $D_{n}$ must omit at least one prime of $n$ from its
prime factorization.

  6. vi.

$D_{n}$ is regular iff $n=(pq)^{m}$ for some positive integer $m$. If
$n=p^{m}q^{r},m\neq r$, then $D_{n}=K_{m,n}$ which is not regular. Then, if
$n$ has more than two distinct primes in it’s prime factorization, $p$ and
$pq$ are vertices with a different degrees. Every vertex that shares an edge
with $pq$ shares an edge with $p$, but $p$ shares an edge with $q$ while $pq$
does not, making the graph non-regular.

  7. vii.

In [9], it is discussed that the girth of the zero divisor graph of any poset
is 3, 4, or $\infty$. The girth of $D_{n}$ is $\infty$ iff $n=p^{m}q$, where
$p$ and $q$ are two distinct primes and $m$ is a positive integers bigger than
$1$. The girth of $D_{n}$ is $4$, if and only if $n=p^{m}q^{r}$, where $p$ and
$q$ are two distinct primes and $m$ and $r$ are both positive integers bigger
than $1$. Otherwise, the girth of $D_{n}$ is $3$, because if $n$ has at least
$3$ different prime factors $p$, $q$ and $r$, then $p-q-r-p$ is a triangle in
$D_{n}$.

  8. viii.

$D_{n}$ is not perfect if $n$ is the product of least five different primes
$p,q,r,s,t$ in it’s prime factorization, then $ps-qt-pr-qs-tr-ps$ is a cycle
of length five in $D_{n}$. Hence by Strong perfect graph theorem $D_{n}$ is
not perfect.
Suppose $n$ has 4 distinct prime factors $p$, $q$, $r$ and $s$. Assume there
is an odd cycle of length 5 or greater that contains a vertex $v$ that is the
product of two such primes. Let $v=p^{x}q^{y}$. Then the two neighbors of $v$
cannot be a multiple of $p$ or $q$. Suppose the neighbors both consists of
$r^{a}$ for some positive integer $a$. Then, we get part of the cycle as
$r^{a}-p^{x}q^{y}-r^{b}$ for another positive integer $b$. Then, $r^{a}$ will
necessarily share an edge with the other neighbors of $r^{b}$ making the cycle
length 4. So the neighbors of $v$ must have both $r$ and $s$. Additionally,
these part of the cycle must be of the form $r^{a}-p^{x}q^{y}-r^{w}s^{z}$,
otherwise we get a cycle of length $4$ again. But any vertex that shares an
edge with $r^{w}s^{z}$ must also share an edge with $r^{a}$ making such a
cycle impossible. This means any odd cycle length greater than 5 cannot
contain a vertex with two or more prime factors, making an odd cycle length
greater than 4 impossible.The other two situations when $v$ consists of only
one prime, or three primes also gives contradiction.Thus $D$ is perfect iff
$n$ has 4 or fewer prime factors (the $n$ $<4$ case follows).

  9. ix.

$D_{n}$ is chordal iff $n=p^{m}q$ or $n=pqr$ where $p$, $q$ and $r$ are
distinct primes and $m\geq 1$. For if $n$ is not of that form,
$p-q-p^{2}-q^{2}-p$ or $p-q-p^{2}-qr-p$ or $p-r-pq-rs-p$ will give holes of
length greater than $3$ in respective $D_{n}$’s.

  10. x.

Let, $n$ be a square free positive integer. Then, it’s simplicial vertices are
precisely those factors of $n$ which misses exactly one prime in it’s prime
factorization. Now, suppose $n$ is not square free. Then, if all primes in
it’s prime factorization are not square free, it has no simplicial vertex.
Otherwise, the simplicial vertices are precisely those which misses exactly
one square free prime factor. For example, if $n=p^{2}q^{2}r$, $pq$, $p^{2}q$,
$pq^{2}$ and $p^{2}q^{2}$ are the only simplicial vertices because $r$ is the
only square free prime factor.

  11. xi.

The only planar $D_{n}$ has $n$ of the form $n=p^{m}q$, $p^{m}q^{2}$, $pqr$ or
$p^{2}qr$. First, let $n$ have only 2 prime factors. We will first examine
this case. If $n=p^{m}q^{l}$ where $l\geq 3$ and $m\geq 3$, then $K_{3,3}$ is
a subgraph of $D_{n}$ and therefore a minor of $D_{n}$. Then by Wagner’s
theorem, $D_{n}$ is non planar. But in the case of $p^{m}q$, $D_{n}$ is a
star, so it is planar. And in the case of $p^{m}q^{2}$, the graph can be drawn
without any crossing edges. Next, let’s examine $n$ with 3 prime factors. If
$n=pqr$ or $n=p^{2}qr$ the graph is clearly planar if drawn. But, if
$n=p^{m}qr$ where $m\geq 3$, The subgraph consisting of $p$, $p^{2}$, $p^{3}$,
$q$, $r$ and $qr$ form $K_{3,3}$ if we delete the edge between $q$ and $r$.
Then by Wagner’s theorem the graph is non-planar since $K_{3,3}$ is a minor.
Next, if $n=p^{m}q^{l}r$, where $m\geq 2$ and $l\geq 2$ the set of vertices
$q$, $q^{2}$, $p$, $p^{2}$, $r$, $pr$ and $qr$ is a subdivision of $K_{5}$.
Then, by Kuratowski’s theorem, the graph is non-planar. So the only planar
$D_{n}$ with only 3 primes in $n$ are $pqr$ and $p^{2}qr$. Lastly, consider
the case where $n$ has 4 primes in its prime factorization, $n=pqrs$. Then,
the vertex set of $p$, $q$, $r$, $s$, $pq$ and $rs$ can be made isomorphic to
$K_{5}$ by contracting the edge between $pq$ and $rs$ to make a single vertex.
Therefore, $K_{5}$ is a minor of $D_{n}$ for this case, and by Wagner’s
theorem the graph is non-planar.

  12. xii.

$D_{n}$ is Eulerian iff the power of each prime in the prime factorization of
$n$ is even. For, if $n$ has a prime $p^{\alpha}$ that appears in it’s prime
factorization where $\alpha$ is odd, then the vertex $\frac{n}{p^{\alpha}}$
has odd degree, otherwise every vertex has even degree.

  13. xiii.

If $n$ is square free, then we have the edge cardinality of $D_{n}$ as
$\sum_{i=1}^{r-1}2^{r-i-1}\binom{r}{i}-2^{r-1}-1$, where $r$ is the number of
distinct primes of $n$. For, if we consider $n=p_{1}p_{2}\cdots p_{r}$, where
$p_{i}$’s are distinct primes, then the degree of each vertex $p_{i}$ is
$\sum_{i=1}^{r-1}\binom{r-1}{i}=2^{r-1}-1$ giving $r(2^{r-1}-1)$ to the degree
sum of the vertices. Similarly each vertex $p_{i}p_{j}$ is adjacent to
$\sum_{i=1}^{r-2}\binom{r-2}{i}=2^{r-2}-1$ many vertices, giving
$\binom{r}{2}(2^{r-1}-2)$ in the degree sum. Proceeding in this way, we obtain
the sum of the vertex degrees are
$\sum_{i=1}^{r-1}\binom{r}{i}(2^{r-i}-1)=\sum_{i=1}^{r-1}\binom{r}{i}2^{r-i}-2^{r}-2$.
Then, as the sum of vertex degrees is twice the edge cardinalities the result
follows.

  14. xiv.

We have a lower bound for Independence number of $D_{n}$. Let,
$n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{r}^{\alpha_{r}}$, where
$p_{i}$’s are distinct primes.Then if $I$ is the independence number of
$D_{n}$,
$I\geq Max_{1\leq i\leq
r}[\alpha_{i}\\{1+\sum\alpha_{i_{1}}\alpha_{i_{2}}\cdots\alpha_{i_{l}}|\alpha_{i}\neq\alpha_{i_{j}}\neq\alpha_{i_{k}},j,k\in\\{1,2,\cdots
l\\}\\}]$, $\\{\alpha_{i_{1}},\alpha_{i_{2}}\cdots\alpha_{i_{l}}\\}$ varies
over all non empty proper subset of
$\\{\alpha_{1},\alpha_{2}\cdots\alpha_{i-1},\alpha_{i+1}\cdots\alpha_{r}\\}$

###### Proof.

Consider any independent set containing $p_{i}$ from the list of primes in the
prime factorization of $n$. Then, the largest possible independent set
containing $p_{i}$, will have $p_{i}$ as a factor in all it’s vertices. So,
that must contain $p_{i},p_{i}^{2},\cdots,p_{i}^{\alpha_{i}}$ giving
$\alpha_{i}$ many vertices in the independent set. In order to maximize the
cardinality of the set, we need to consider all possible factors of $n$ that
has a factor $p_{i}$ and that misses atleast one prime in the prime
factorization of $n$. Thus we get
$p_{i}p_{1},p_{i}p_{1}^{2},\cdots
p_{i}p_{1}^{\alpha_{1}},p_{i}p_{2},p_{i}p_{2}^{2},\cdots
p_{i}p_{2}^{\alpha_{2}},\cdots p_{i}p_{r},p_{i}p_{r}^{2},\cdots
p_{i}p_{r}^{\alpha_{r}}$ are inside the independent set giving
$\alpha_{i}(\alpha_{1}+\alpha_{2}+\cdots\alpha_{i-1}+\alpha_{i+1}+\cdots\alpha_{r})=\alpha_{i}\sum_{j=1,j\neq
i}^{r}\alpha_{j}$ many vertices. Similarly, we get more
$\alpha_{i}\sum_{j=1,i\neq j\neq k}^{r}\alpha_{j}\alpha_{k}$ many vertices
from the factors of $n$ that contains $p_{i}$ and that are product of three
primes. Proceeding in this way get the necessary result. ∎

  15. xv.

Let, $n$ be square free. Then, a lower bound of the Independence number of
$D_{n}$ is $2^{r-1}-r$, where $r$ is the number of prime factors of $n$. If,
$n=p_{1}p_{2}\cdots p_{r}$, where $p_{i}$’s are distinct primes, then whenever
$I$ is the independence number of $D_{n}$, $I\geq 2^{r-1}-r$.

###### Proof.

Consider any independent set in $D_{n}$. If we pick up any element from that
set, that is divisible by some $p_{i}$, then, all possible proper divisors of
$n$, that has $p_{i}$ as a factor forms an Independent set of $D_{n}$ and
cardinality of that set is $2^{r-1}-r$. Hence the result follows. ∎

##  6\. acknowledgment

The authors acknowledge Dr. Lisa DeMeyer for introducing this topic to us by
an excellent presentation, which motivated us to work in this area.

## References

  * [1] I. Beck, _Coloring of commutative rings_ , J. Algebra, 116 no. 1 (1988), 208-226.
  * [2] E. E. AbdAlJawad, H. Al-Ezeh, _Domination and Independence Numbers of $\Gamma(\mathbb{Z}_{n})$_, International Mathematical Forum, 3, 2008, no. 11, 503 - 511.
  * [3] Smith, Bennett, _”Perfect Zero-Divisor Graphs of $Z_{n}$, _, Rose-Hulman Undergraduate Mathematics Journal: Vol. 17 : Iss. 2 , Article 6, 2016.
  * [4] D. F. Anderson, P. S. Livingston, _The zero-divisor graph of a commutative ring_ , J. Algebra, 217 no. 2 (1999), 434-447.
  * [5] Livingston, Philip S., _Structure in Zero-Divisor Graphs of Commutative Rings_ , Master’s Thesis, University of Tennessee, 1997. https://trace.tennessee.edu/utkgradthes/1803.
  * [6] D. D. Anderson, M. Naseer, _Beck’s coloring of a commutative ring_ , Journal of Algebra, Vol. 159, 500 - 514, 1993.
  * [7] S. K. Nimbhorkar, M. P. Wasadikar, L. Demeyer, _Coloring of Meet-Semilattices_ , Ars Combinatoria, Vol. 84, 97 - 104, 2007.
  * [8] Z Xue, S. Liu, _Zero divisors of partially ordered sets_ , Applied Mathematics Letters, Volume 23, Issue 4, April 2010, Pages 449-452.
  * [9] M. Ali, A. K. Das, H. R. Maimani, M. R. Pournaki, S. Yassemi _On the diameter and girth of zero divisor graphs of posets_ , Discrete Applied Mathematics, Volume 160, Issue 9, June 2012, Pages 1319-1324.
  * [10] R. Halaš, M. Jukl, _On Beck’s coloring of posets_ , Discrete Mathematics, Volume 309, Issue 13, 6 July 2009, Pages 4584-4589.