# On the Line Graph of the Zero Divisor Graph for the Ring of Gaussian Integers Modulon

Authors: Khalida Nazzal; Manal Ghanem
Journal: International Journal of Combinatorics
 (2012)

---

## Abstract

LetΓ(ℤn[i]) be the zero divisor graph for the ring of the Gaussian integers modulo n. Several properties of the line graph of Γ(ℤn[i]), L(Γ(ℤn[i])) are studied. It is determined when L(Γ(ℤn[i])) is Eulerian, Hamiltonian, or planer. The girth, the diameter, the radius, and the chromatic and clique numbers of this graph are found. In addition, the domination number of L(Γ(ℤn[i])) is given when n is a power of a prime. On the other hand, several graph invariants for Γ(ℤn[i]) are also determined.


---

## Body

## 1. Introduction

The study of zero divisor graphs of commutative rings reveals interesting relations between ring theory and graph theory; algebraic tools help understand graphs properties and vise versa. In 1988, Beck [1] defined the concept of zero divisor graph of a commutative ring R, where the vertices of this graph are all elements in the ring and two vertices x, y are adjacent if and only if xy=0. Anderson and Livingston [2] modified the definition of zero divisor graphs by restricting the vertices to the nonzero zero divisors of the ring R. Further study of zero divisor graphs by Anderson et al. [3] investigated several graph theoretic properties, such as the number of cliques in Γ(R). They also gave some cases in which Γ(R) is planer. On the other hand, they answered the question when Γ(R1)≅Γ(R2) for some specified types of rings R1 and R2. Akbari and Mohammadian [4] improved on those results. Γ(R) for rings R which satisfy certain conditions are discussed by Anderson and Badawi [5]. The zero divisor graph of the ring of integers modulo n was extensively studied in [6–10].In 2008, Abu Osba et al. [11] introduced the zero divisor graphs for the ring of Gaussian integers modulo n, Γ(ℤn[i]), where they studied several graph properties and determined several graph invariants for Γ(ℤn[i]). Further properties of the zero divisor graphs for the ring of Gaussian integers modulo n are investigated in [12].In this paper, we study the line graph ofΓ(ℤn[i]). We organized our work as follows: some basic definitions and terminology are given in Section 2. In Sections 3 and 4, we answer the question when is the line graph L(Γ(ℤn[i])) Eulerian, Hamiltonian, or planer. In Section 5, the chromatic and clique numbers of L(Γ(ℤn[i])) are found. While the diameter, the girth and the radius of L(Γ(ℤn[i])) are determined in Sections 6 and 7, respectively. Finally, the last two sections discuss the domination number of Γ(ℤn[i]) and L(Γ(ℤn[i])) as well as the independence and clique numbers of Γ(ℤn[i]).


## 2. Preliminaries

The set of Gaussian integers is defined byℤ[i]={a+bi:a,b∈ℤandi=-1}.A prime Gaussian integer is one of the following:(i)
(1+i) or (1-i),(ii)
q, where q is a prime integer and q≡3(mod4),(iii)
a+bi, a-bi, where a2+b2=p, p is a prime integer and p≡1(mod4).It is clear thatℤn[i] is a ring with addition and multiplications modulo n. Throughout this paper, p will be used to denote a prime integer which is congruent to 1 modulo 4, while q will denote a prime integer which is congruent to 3 modulo 4. Since ℤn[i] is finite, each element in ℤn[i] is either a zero divisor or a unit. Also, since ℤ[i] is a unique factorization domain, each integer n can be uniquely factorized as n=∏j=1kπjmj where πj′s are Gaussian prime integers and mj′s are positive integers.The zero divisor graph of a commutative ringR denoted by Γ(R), is the graph whose vertices is the set of all nonzero zero divisors of R, and edge set E(Γ(R))={xy:x,y∈V(Γ(R))andxy=0}. The line graph L(G) of a graph G is defined to be the graph whose vertices are the edges of G, with two vertices being adjacent if the corresponding edges share a vertex in G. For Γ(ℤn[i]), if n=2, then this graph is one vertex, while if n=q, then Γ(ℤn[i])=K0. Throughout this paper, all rings, R, are commutative with unity.For a connected graphG, the distance, d(u,v), between two vertices u and v is the minimum of the lengths of all u-v paths of G. The eccentricity of a vertex v in G is the maximum distance from v to any vertex in G. The radius of G, rad(G), is the minimum eccentricity among the vertices of G. The diameter of G, diam(G), is the maximum eccentricity among the vertices of G. The girth of G, g(G), is the length of a shortest cycle in G. The center of G is the set of all vertices of G with eccentricity equal to the radius. If G has a walk that traverses each edge exactly once goes through all vertices and ends at the starting vertex, then G is called Eulerian. A graph is called Hamiltonian if there exists a cycle containing every vertex. The chromatic number of a graph G, χ(G), is the minimum k such that G is k-colorable (i.e., can be colored using k different colors such that no two adjacent vertices have the same color). The clique number, ω(G), of a graph G is the maximum order among the complete subgraphs of G. A subset D of the vertex set V(G) is said to be independent if no two vertices in this set are adjacent. The independence number of G, β(G), is the maximum cardinality of all independent sets in G. A subset D of the vertex set V(G) of a graph G is a dominating set in G if each vertex of G, not in D, is adjacent to at least one vertex of D. The minimum cardinality of all dominating sets in G, γ(G), is called the domination number of G. Edge dominating sets are defined analogously. The minimum cardinality of all edge dominating sets in G, γ̀(G), is called the edge domination number of G. The minimum cardinality of all independent edge dominating sets, γ´i(G), is called the independence edge domination number of G. The maximum vertex degree of a graph G will be denoted by Δ(G).


## 3. When IsL(Γ(ℤn[i])) Eulerian?

Now it is characterized when the line graphL(Γ(ℤn[i])) is Eulerian. Before proceeding, we prove the following lemma.Lemma 3.1.
(i) Every vertex ofΓ(ℤn[i]) has even degree if and only if n=2, p or n is a composite integer which is a product of distinct odd primes.
(ii) Ifn=tm, m≥2 and n≠q2, then Γ(ℤn[i]) has a vertex of odd degree and another of even degree.
(iii) Every vertex ofΓ(ℤn[i]) has odd degree if and only if n=q2.Proof.
(i) Since the graphG is Eulerian if and only if each vertex has an even degree by Theorem 29 of [11], the result holds.
(ii) Assume thatn=tm,t is prime, m≥2 and n≠q2. Then we have three cases.
Case I (t=2).
Then deg(1+i)=1 and deg(2m-1+2m-1i)=22m-1-2.Case II (t is an odd prime and m>2).
By Theorem 23 of [11], Γ(ℤn[i]) has a vertex of degree t2k-1-1, where 1≤k<m/2 and a vertex of degree t2k-2, where m/2≤k<m.Case III (t=p=a2+b2 and m=2).
Sincedeg(a+ib)=|〈p(a-ib)〉|-1 and |〈p(a-ib)〉| divides |ℤp2|, |〈p(a-ib)〉| is odd and hence deg(a+ib) is even. Then by using part (i), the result holds.(iii) (⇒) Let n=Πj=1kajmj,k≥2, and x̅j=(xt), where
(3.1)xt={1,ift=j,0,otherwise.
Now if all aj′s are odd primes, then deg(x̅j)=n/(ajmj)-1 and if a1=2, then deg(x̅1)=(n/2m1)-1.
(⇐) Note that, Γ(ℤq2[i])≅Kq2-1. So, deg(v)=q2-2 for every vertex v in Γ(ℤq2[i]).SinceL(Γ(R)) is Eulerian if and only if deg(v) is even for every v∈Γ(R) or deg(v) is odd for every v∈Γ(R), [9], together with Lemma  3.1 and Theorem 26 of [11], the following theorem is obtained.Theorem 3.2.
(i)L(Γ(ℤn[i]) is Eulerian graph if and only if n=2,p,q2, or n is a composite integer which is a product of distinct odd primes.
(ii)L(Γ(ℤn[i]) is Eulerian graph does not necessarily imply that Γ(ℤn[i]) is Eulerian.


## 4. When IsL(Γ(ℤn[i])) Hamiltonian or Planner?

First we determine which graphs,Γ(ℤn[i]), are Hamiltonian. Before this paper comes to the light, a recent article by Abu Osba et al. [12] reached to similar results concerning Hamiltonian Γ(ℤn[i]). However, we present our proof since it is simpler and shorter. The proof makes use of the following theorem.Theorem 4.1 (see [4]).
LetR be a finite principal ideal ring, if Γ(R) is Hamiltonian, then it is either a complete graph or a complete bipartite graph.Theorem 4.2.
The graphΓ(ℤn[i]) is Hamiltonian if and only if n=p or q2.Proof.
Sinceℤn[i] is a finite principal ideal ring, Γ(ℤn[i]) is a complete graph or a complete bipartite graph if Γ(ℤn[i]) is Hamiltonian. But the graph Γ(ℤn[i]) is complete if and only if n=q2, and it is complete bipartite if and only if n=p or q1q2, where q1<q2, [11]. On the other hand, a complete bipartite graph Km,n is Hamiltonian if and only if m=n. So the result holds.Note thatΓ(ℤq1q2[i]) is not Hamiltonian and hence the converse of Theorem 4.1 is not true.Next, we move to the line graphsL(Γ(ℤn[i])). Before proceeding, we present the following theorem.Theorem 4.3.
(i) IfG is a graph of diameter at most 2 with |V(G)|≥4, then L(G) is Hamiltonian, see [13].
(ii) The line graph of an Eulerian graph is both Hamiltonian and Eulerian, see [14].Ifn=p, 2m, or qm, where m≥2, then diam(Γ(ℤn[i]))≤2. On the other hand, if n=2,p or n is a composite odd integer which is a product of distinct primes, then Γ(ℤn[i]) is Eulerian, [11]. Thus the following corollary is obtained.Corollary 4.4.
(i) Ifn=p,  2m, or qm, where m≥2, then L(Γ(ℤn[i])) is Hamiltonian.
(ii) Ifn is a composite odd integer which is a product of distinct primes, then L(Γ(ℤn[i])) is both Eulerian and Hamiltonian.Now, we discuss planarity of the graphL(Γ(ℤn[i])).A graphG is planar if it can be drawn in the plane without any edge crossing. The following theorem gives necessary and sufficient conditions on a graph G so that the line graph L(G) is planer.Theorem 4.5 (see [15]).
A nonempty graphG has a planer line graph L(G) if and only if(i)
G is planer,(ii)
Δ(G)≤4,(iii)
ifdegG(v)=4, then v is a cut vertex.Recall thatΓ(ℤn[i]) is planer if and only if n=2 or n=4, [11]. But L(Γ(ℤ4[i])) is not planer since Δ(Γ(ℤ4[i]))=7>4. Therefore, we get the following theorem.Theorem 4.6.
The graphL(Γ(ℤn[i])) is never planer.


## 5. The Chromatic and Clique Numbers ofL(Γ(ℤn[i]))

IfR is a finite ring, then χ′(Γ(R))=Δ(Γ(R)), unless Γ(R) is complete graph of odd order, [4]. Note that, the only complete graph Γ(ℤn[i]) occurs when n=q2. However, in this case the order of the graph is q2-1 which is even, so χ′(Γ(ℤn[i]))=Δ(Γ(ℤn[i])). Moreover, since the edge coloring of any graph leads to a vertex coloring of its line graph, we obtain χ(L(Γ(ℤn[i])))=Δ(Γ(ℤn[i])). Clearly, χ(G)≥ω(G). On the other hand, the line graph of G has a complete subgraph of order Δ(G). Thus ω(L(Γ(ℤn[i])))≥Δ(Γ(ℤn[i])). Observe that if n=2m or qm,m≥2, then Γ(ℤn[i]) has a vertex which is adjacent to every other vertex in Γ(ℤn[i]). While if n=pm,m≥1, then ℤpm[i]≅ℤpm×ℤpm. Thus Δ(Γ(ℤpm[i]))=p2m-1-1. This leads to the following Theorem.Theorem 5.1.
(5.1)ω(L(Γ(Zn[i])))=χ(L(Γ(Zn[i])))={22m-1-2,ifn=2m,m≥2,q2m-2-2,ifn=qm,m≥2,p2m-1-1,ifn=pm,m≥1.Finally, ifn=2m∏j=1rpjrj∏j=1lqj∏j=1sqjsj, where sj≥2 and m,rj≥1, then the clique number and the chromatic number for the graph L(Γ(ℤn[i])) is given by the following theorem.Theorem 5.2.
n=2m∏j=1rpjrj∏j=1lqj∏j=1sqjsj, where m,rj≥1 and sj≥2, then
(5.2)ω(L(Γ(Zn[i])))=χ(L(Γ(Zn[i])))=(22m-1-1)∏j=1r(pj2rj-1)∏j=1s(qj2sj-2-1)-1.Proof..
The result follows by computingΔ(Γ(ℤn[i])), since Δ(Γ(ℤn[i]))=ω(L(Γ(ℤn[i])))=χ(L(Γ(ℤn[i]))).


## 6. The Diameter ofL(Γ(ℤn[i]))

Now, we will find the diameter of the line graphL(Γ(ℤn[i])).First, we will prove thatdiam(L(Γ(ℤn[i])))=2 when n=2m or n=qm.Lemma 6.1.
(i) Ifn=2m,m≥2, then there are no a+bi,c+di∈ℤn[i], where a,b,c,d are odd integers such that (a+bi)(c+di)≡0(mod4).
(ii) Ifn=qm,m≥2 then there are no a+bi,c+di∈ℤn[i] where a,b,c,d are relatively prime with q, such that (a+bi)(c+di)≡0(modq).Proof..
(i) Assume that(a+bi)(c+di)≡0(mod4). Then ac-bd≡0(mod4) and ad+bc≡0(mod4). Since a,b,c,d are odd integers, a=2a1+1, b=2b1+1, c=2c1+1, and d=2d1+1 for some a1,b1,c1,d1∈ℤ. So ac-bd≡a1+c1+b1+d1≡0(mod2). And ad + bc≡a1 + c1 + b1 + d1≡1(mod2), a contradiction.
(ii) Assume that(a+bi)(c+di)≡0(modq). Then ac-bd≡0(modq) and ad+bc≡0(modq). Since a,b,c,d are relatively prime with q, we have a=qa1+a2, b=qb1+b2, c=qc1+c2 and d=qd1+d2, where 0<a2,b2,c2,d2<q. So(6.1)ac-bd≡a2c2-b2d2≡0(mod⁡q),(6.2)ad+bc≡a2d2+b2c2≡0(mod⁡q).
Multiplying (6.1) by c2 and (6.2) by d2 and adding gives a2(c22+d22)≡0(modq). Then q|a2 or q|(c22+d22). Since a2<q, q|(c22+d22). Therefore, c22+d22≡0(modq), and hence c2≡d2≡0(modq), a contradiction.So, we conclude the following.Theorem 6.2.
Ifn=2m or qm and m≥2, then diam(L(Γ(ℤn[i])))=2.Proof.
(i) Suppose thatn=2m,m≥2. Then,(1)
x=a2t+b2ki where a,b are odd and t≠k or t=k≥⌈m/2⌉ implies that ann(x)={c2r+d2si:canddareoddandr,s≥m-min{t,k}},(2)
x=2t(a+bi) where a,b are odd and t<⌈m/2⌉, then ann(x)={c2r+d2si:canddareoddandr,s≥m-t}∪{2m-t-1(c+di):canddareodd}.
Moreover,d([2t(a1+b1i),2m-t-1(c1+d1i)],[2s(a2+b2i),2m-s-1(c2+d2i)])=2 if t≤s<⌈m/2⌉. Since [2s(a2+b2i),2m-t-1(c1+d1i)]∈V(L(Γ(ℤn[i]))).
(ii) Suppose thatn=qm,m≥2. Let x=aqt+bqki and a,b∈U(ℤn). Then ann(x)={cqr+dqsi:r,s≥m-min{t,k}}. Moreover, d([a1qr1+b1qs1i,c1qt1+d1qk1i], [a2qr2+b2qs2i,c2qt2+d2qk2i])=2 since r1,s1,t2,k2≥⌈m/2⌉ implies that [a1qr1+b1qs1i,c2qt2+d2qk2i]∈V(L(Γ(ℤn[i]))).From Theorems 3.1 and 3.3 of [9], 2≤diam(L(Γ(ℤn[i])))≤3. In L(Γ(ℤpm[i])), where p=a2+b2 and m≥2, d([p,pm-1],[(a+ib)m,(a-ib)m])=3. So, diam(L(Γ(ℤpm[i])))=3.Theorem 6.3.
(i) Ifn=st, where s,t are two distinct primes and s≠p or t≠p, then diam(L(Γ(ℤn[i])))=2.
(ii) Ifn=st2 are two distinct primes and s,t≠p, then diam(L(Γ(ℤn[i])))=2.Proof.
First note that diam(L(Γ(R)))≥2, [9] and for n=n1n2 with g.c.d(n1,n2)=1, ℤn[i]≅ℤn1[i]×ℤn2[i].(i)
Case I: Ifn=qp or n=2p where p=a2+b2, then V(L(Γ(ℤn[i])))={[(u,α(a+bi)),(0,β(a-bi))]}∪{[(0,α(a+bi)),(u,β(a-bi))]}∪{[(u,0),(0,v)]}.Case II: Ifn=2qorn=q1q2, then
(6.3)V(L(Γ(Zn[i])))={[(u,0),(0,v)]:u,v≠0}.(ii)
Note thatV(L(Γ(ℤn[i])))={[(u,αt),(0,βt)]}∪{[(u,0),(0,v)]:u,v,α,β≠0}.Theorem 6.4.
(i) Ifn=sp2, where s is prime and p=a2+b2, then diam(L(Γ(ℤn[i])))=3.
(ii) Ifn=p1mp2l, where p1=a12+b12, p2=a22+b22 and m,l≥1, then diam(L(Γ(ℤn[i])))=3.
(iii) Ifn=pmtl, where p=a2+b2, m≥1,l≥2, and g.c.d(p,t)=1, then diam(L(Γ(ℤn[i])))=3.
(iv) Ifn=smtl where s,t are distinct primes and m,l≥2, then diam(L(Γ(ℤn[i])))=3.Proof.
(i) Letv1=[(0,(a+bi)2),(1,(a-bi)2)] and v2=[(0,(a-bi)(a+bi)),(1,(a-bi)(a+bi))]. Then d(v1,v2)=3.
(ii) Letv=[((a1+b1i)m,(a2+b2i)l),((a1-b1i)m,(a2-b2i)l)]. Then d(v,[(1,0),(0,1)])=3.
(iii) Letv=[((a+bi)m,t),((a-bi)m,tl-1)]. Then d(v,[(1,0),(0,1)])=3.
(iv) Letv=[(s,t),(sm-1,tl-1)]. Then d(v,[(1,0),(0,1)])=3.Theorem 6.5.
(i) IfR1,R2,R3 are fields and R=R1×R2×R3, then diam(L(Γ(R)))=2.
(ii) IfR1,R2,R3 are finite rings and Ri is not a field for some i∈{1,2,3} and R=R1×R2×R3, then diam(L(Γ(R)))=3.
(iii) IfR=Πi=1kRi where k≥4, then diam(L(Γ(R)))=3.Proof.
(i) Let[(a1,a2,a3),(b1,b2,b3)][(c1,c2,c3),(d1,d2,d3)]∈E(L(Γ(R))). Since R1,R2,R3 are fields, (a1,a2,a3) or (b1,b2,b3) has exactly two components equal 0. W.L.O.G. let (a1,a2,a3)=(a1,0,0) and a1≠0. Since c1d1=0, c1=0 or d1=0. Say c1=0, then [(a1,a2,a3),(c1,c2,c3)]∈E(L(Γ(R))). So, diam(L(Γ(R)))=2.
(ii) Suppose thatR1 is not a field. Let x,y∈R1* such that xy=0. Then d([(x,0,1),(y,1,0)],[(0,1,1),(1,0,0)])=3.
(iii) Letx=(xj), where xj=1ifj=1,2 and 0 otherwise, y=(yj), where yj=1ifj=3,4 and 0 otherwise, z=(zj), where zj=1ifj=2,3 and 0 otherwise and w=(wj), where wj=1ifj=1,4 and 0 otherwise. Then d([x,y],[z,w])=3.Summarizing the above results, we get the following theorem.Theorem 6.6.
(i)diam(L(Γ(ℤn[i])))=2 if and only if n=p,2q,q1q2,q1q2q3,2q1q2,4q,2q2,2p,qp or  n=2m,qm with m≥2.
(ii)diam(L(Γ(ℤn[i])))=3 otherwise.


## 7. The Girth and the Radius ofL(Γ(ℤn[i]))

In this section, we give a complete characterization of the girth and the radius ofL(Γ(ℤn[i])).Since for any commutative ringR, L(Γ(R)) is a tree if and only if Γ(R)=K2 or K1,2 [9], L(Γ(ℤn[i])) is never a tree. On the other hand, if L(Γ(R)) contains a cycle, then g(L(Γ(R)))≤4 where equality holds only if R=ℤ3×ℤ3, [9].Consequently, the following result holds.Theorem 7.1.
g(L(Γ(ℤn[i])))=3.Next, we prove that the radius of the line graphL(Γ(ℤn[i])) equals 2.Sincediam(L(Γ(R)))≤3, [9] and rad(G)≤diam(G) for any graph G, rad(L(Γ(R)))≤3.Lemma 7.2.
If there exists a vertexv∈L(Γ(ℤn[i])) with eccentricity 2, then rad(L(Γ(ℤn[i]))=2Proof.
Note that,L(Γ(ℤn[i])) has no spanning star graph, since if a,b∈V(Γ(ℤn[i])) such that a≠b and ab=0, then d([a,b],[ai,bi])>1.Theorem 7.3.
Ifn=2m, n=qm, m≥2 or n=pm,  m≥1, then rad(L(Γ(ℤn[i]))=2.Proof.
(1)
Ifn=2m,m≥2, then d([2m-1+2m-1i,2],[x,y])≤2forall[x,y]∈V(L(Γ(ℤn[i])).(2)
Ifn=qm,m≥2, then d([qm-1,q],[x,y])≤2 for all [x,y]∈V(L(Γ(ℤn[i])).(3)
Ifn=pm,m≥1, then d([(a+bi)m(a-bi)m-1,(a-bi)m(a+bi)m-1],[x,y])≤2 for all [x,y]∈V(L(Γ(ℤn[i])).Theorem 7.4.
Ifn=rmt, where r=2,q, or p and m≥1,  g.c.d(r,t)=1,  then rad(L(Γ(ℤn[i]))=2.Proof.
(1)
Ifr=2 or q, then d([(rm-1,0),(r,1)],[(x,y),(t,s)])≤2 for all [(x,y),(t,s)]∈V(L(Γ(ℤn[i])).(2)
Ifr=p=a2+b2, then d([((a+bi)m(a-bi)m-1,0), ((a-bi)m(a+bi)m-1,0)], [(x,y),(t,s)])≤2 for all [(x,y),(t,s)]∈V(L(Γ(ℤn[i])).Summarizing the above results, we get the following.Theorem 7.5.
The radius of the line graphL(Γ(ℤn[i]) equals 2.


## 8. The Domination Number ofΓ(ℤn[i])

Pervious results concerning the domination number ofΓ(ℤn[i]) are very restricted; Abu Osba et al. [11] answered the question “when is the domination number 1 or 2?”. Here we find the domination number of the graph Γ(ℤn[i]). Two independent proofs reflecting two different viewpoints are given, the first proof depends on ring theory. While the second proof is constructive in the sense that it does not only give the domination number of Γ(ℤn[i]), but also gives a minimum dominating set of this graph. This dominating set, as we will see, reveals to have interesting properties.Theorem 8.1 (see [16]).
LetR be a finite commutative ring with identity that is not an integral domain. If Γ(R) is not a star graph, then the domination number equals the number of distinct maximal ideals of R.Theorem 8.2.
Ifn=∏j=1kπjmj, where k≥1 and πj′s are distinct gaussian prime and mj′s are positive integers and n≠2 or q. Then γ(Γ(ℤn[i]))=k, if n is odd, and γ(Γ(ℤn[i]))=k-1,  if n is even.Proof.
(I)(1) If n=2m, then 〈1+i〉 is the unique maximal ideal of ℤn[i].
(2) If n=qm, then 〈q〉 is the unique maximal ideal of ℤn[i].
(3) If n=pm where p=a2+b2, then 〈a+bi〉 and 〈a-bi〉 are the only distinct maximal ideals of ℤn[i].
(4) If n=∏j=1kπjmj is odd then 〈πj〉×∏t=1,t≠jk(ℤ[i]/〈πtmt〉) are the only maximal ideals of ℤn[i].
(5) If n=∏j=1kπjmj is even then π1=(1+i),π2=(1-i) and 〈πj〉×∏t=1,t≠jk(ℤ[i]/〈πtmt〉) where j≠2 are the only distinct maximal ideals of ℤn[i]. Finally, since Γ(ℤn[i]) is never a star graph [11], the result holds.Proof.
(II) We have two cases.
Case I:n is odd. Then it is easy to see that D={Pj=π1m1π2m2…πjmj-1…πkmk:1≤j≤k} is a dominating set of Γ(ℤn[i]). To show that D is a minimum dominating set, assume that D1 is a minimum dominating set such that there is no x=sPj, g.c.d(s,πj)=1 belongs to D1 for some 1≤j≤k. Then Tj={πj,2πj}⊆D1. So, (D1-Tj)∪{Pj} is a dominating set of Γ(ℤn[i]), a contradiction.
Case II:n is even. Then π1=(1+i),π2=(1-i). Similar to case I, we can see that D={Pj=π1m1π2m2…πjmj-1…πkmk:1≤j≤k,j≠2} is a minimum dominating set of Γ(ℤn[i]).If a dominating setD induces a complete graph, then, D is called clique dominating set, the clique domination number is the cardinality of a minimum clique dominating set, and is denoted by γcl(G), if every vertex in D is adjacent to another vertex in D, then D is called total dominating set. The minimum cardinality of a total dominating set is called total domination number and is denoted by γt(G). For any graph G, γ(G)≤γt(G)≤γcl(G). Since the suggested dominating set, D, for Γ(ℤn[i]) in the second proof of Theorem 8.2 induces a complete graph, then γ(Γ(ℤn[i]))=γt(Γ(ℤn[i]))=γcl(Γ(ℤn[i])).


## 9. The Domination Number ofL(Γ(ℤn[i]))

In this section we determine the domination number ofL(Γ(ℤn[i])) when n=tm and t is prime.The study of the domination number of the line graph ofG leads to the study of edge or line domination number of G, that is, γ(L(G))=γ′(G). On the other hand, for any graph G, γi′(G)=γ′(G), [17]. Further, if G is the complete bipartite graph Kr,s, then γ′(G)=min(r,s), thus we have the following.Lemma 9.1.
(i)γ(L(Γ(ℤp[i])))=γi′(Γ(ℤp[i]))=γ′(Γ(ℤp[i]))=p-1.
(ii)γ(L(Γ(ℤq1q2[i])))=γi′(Γ(ℤq1q2[i]))=γ′(Γ(ℤq1q2[i]))=q1, where q1<q2.Now, we study the domination number of the line graph ofΓ(ℤn[i]) when n is a power of a prime. The first theorem treats the case n=2m,m≥2. Here we make use of the fact that Γ(ℤ2m[i])≅Γ(ℤ22m), [12].Theorem 9.2.
Forn=2m,m≥2,
(9.1)γ(L(Γ(Zn[i])))=γi′(Γ(Zn[i]))=γ′(Γ(Zn[i]))=⌊12(2m-1)⌋.Proof.
Forj=1,2,…,2m-1, let Aj={α22m-j:α∈{1,3,…,2j-1}}. Note that the sets Aj form a partition to the vertices of Γ(ℤ22m). Let S=⋃j=1mAj and T=⋃j=m+12m-1Aj. Then the set S induces a complete subgraph of Γ(ℤ22m) and the set T form an independent set of it. And each vertex in Ak is adjacent to each vertex in ⋃j=12m-kAj. Γ(ℤ22m) has no other edges. Let D⊂E(Γ(ℤ22m)) be a dominating set of vertices for L(Γ(ℤ22m)) with minimum cardinality. Since, the set S induces a complete subgraph of Γ(ℤ22m) of order 2m-1, then γ(L(Γ(ℤ2m[i])))≥⌊(1/2)(2m-1)⌋. On the other hand, since D dominates all edges in the complete graph 〈S〉, D also dominates every edge joining S to T, recall that T forms an independent set and so γ(L(Γ(ℤ2m[i])))=⌊(1/2)(2m-1)⌋.The proof of Theorem9.2. shows the set T is an independent set with maximum cardinality in Γ(ℤ2m[i]), while the set S induces a complete subgraph with maximum order.So, the following corollary is obtained.Corollary 9.3.
Forn=2m,m≥2, (i)
ω(Γ(ℤn[i]))=2m-1,(ii)
β(Γ(ℤn[i]))=2m(2m-1-1).As another consequence to the proof of the preceding theorem, the following corollary, which gives the degree sequence forΓ(ℤ2m[i]), is obtained.Corollary 9.4.
Forj=1,2,…,2m-1, the graph Γ(ℤ2m[i]) has exactly 2j-1 vertices of degree 22m-j-2 if 1≤j≤m and 2j-1 vertices of degree 22m-j-1 if m+1≤j≤2m-1.Proof.
For eachv∈Aj, where 1≤j≤m,v2=0, so deg(v)=|⋃k=12m-jAk|-1=22m-j-2. And for each v∈Ak, where m+1≤k≤2m-1,v2≠0, so deg(v)=|⋃k=12m-jAk|=22m-j-1.Furthermore, The proof of the above theorem shows that the eccentricity of22m-1 is 1 and the eccentricity of any other vertex in Γ(ℤ22m) is 2, since the vertex 2 is adjacent only to the vertex 22m-1, and for any x∈V(Γ(ℤ2m[i])), 2–22m-1–x, is a path of length 2. This aleads to the following corollary.Corollary 9.5.
The center of the graphΓ(ℤ2m[i]) is the set {2m-1(1+i)}.Next, we we find the domination number of the line graphL(Γ(ℤn[i])) when n=qm,m≥2.Lemma 9.6.
(i) Form≥2, (1)
IfAkj={aqk+bqji:a∈U(ℤqm-k),b∈U(ℤqm-j)}, then |Akj|=(q-1)2q2m-k-j-2 when 1≤k,j≤m-1, |Amj|=qm-j-qm-j-1 and |Akm|=qm-k-qm-k-1 when k,j≠m,(2)
IfS=(⋃⌈m/2⌉≤k,j≤mAkj)-Amm, then |S|=q2⌊m/2⌋-1.
(ii) Form≥3, if T=⋃1≤k,j≤⌈m/2⌉-1Akj, then |T|=q2⌊m/2⌋(q⌈m/2⌉-1)2.Theorem 9.7.
Ifn=qm,m≥2, then γ(L(Γ(ℤn[i])))=γ′(Γ(ℤn[i]))=γi′(Γ(ℤn[i]))=(1/2)(qm-1) if m is even and (1/2)(q2⌊m/2⌋+1) if m is odd.Proof.
LetAkj,S, and T be defined as given in Lemma 9.6. Clearly, the set S induces a complete subgraph of Γ(ℤn[i]) with maximum order if m is even and S∪{q⌊m/2⌋} induces a complete subgraph of Γ(ℤn[i]) with maximum order if m is odd. On other hand if m≥3, then T form an independent set with maximum cardinality. Moreover, if a vertex v belongs to the set Ars, then v is adjacent to every element in Akj where m-min{r,s}≤k,j≤m and k,j≠m at the same time. Γ(ℤn[i]) has no other edges.As a consequence of the proof of Theorem9.7, we conclude the following.Corollary 9.8.
Ifn=qm,m≥2, then (i)
ω(Γ(ℤn[i]))=qm-1 if m is even and q2⌊m/2⌋ if m is odd,(ii)
β(L(Γ(ℤn[i])))=1 if m=2 and β(L(Γ(ℤn[i])))=q2⌊m/2⌋(q⌈m/2⌉-1)2 if m≥3.Corollary 9.9.
Letn=qm, m≥2, and v=aqr+bqsi where a,b∈U(ℤn). Then
(9.2)deg⁡⁡(v)={q2min⁡{r,s}-2,ifr,s≥⌈m2⌉,q2min⁡{r,s}-1,ifrors<⌈m2⌉.Corollary 9.10.
Letn=qm,m≥2. Then(i)
the eccentricity of eachv∈A(m-1)(m-1) is 1 and the eccentricity of any other vertex v∈Γ(ℤn[i]) is 2,(ii)
the center of the graphΓ(ℤn[i]) is the set A(m-1)(m-1),(iii)
the radius of the graphΓ(ℤn[i]) equals 1,(iv)
the diameter of the graphΓ(ℤn[i]) equals 2, for m≥3.Finally, we find the domination number of the line graphL(Γ(ℤn[i])) when n=pm,m≥2.Recall thatℤpm[i]≅ℤpm×ℤpm. Let, Akj={(apk,bpj):a∈U(ℤpm-k),b∈U(ℤpm-j)}. Clearly, the sets Akj,0≤k,j≤m and not both k,j=m or 0, partition the vertices of Γ(ℤpm×ℤpm).Lemma 9.11.
(i) Form≥2:(1)
ifS=(⋃⌈m/2⌉≤k,j≤mAkj)-Amm, then s=|S|=p2⌊m/2⌋-1,(2)
ifL1=⋃0≤k≤⌈m/2⌉-1Akm and L2=⋃0≤k≤⌈m/2⌉-1Amk, then l=|L1|=|L2|=pm-p⌊m/2⌋,
(ii) form≥3:
(1)
ifB=⋃k=1⌈m/2⌉-1⋃j=m-km-1Akj, then b=|B|=(pm-pm-1)(⌈m/2⌉-1)-(pm-1-p⌊m/2⌋),(2)
ifT=⋃0≤k,j≤⌈m/2⌉-1Akj-A0,0, then t=|T|=(pm-1-p⌊m/2⌋)2+2(p-1)(p2m-2-p2m-⌈m/2⌉-1),
(iii) form≥4:
IfW1=⋃k=⌈m/2⌉m-1⋃j=1m-k-1Akj, W2=⋃j=⌈m/2⌉m-1⋃k=1m-j-1Akj and W=W1∪W2, then w=|W|=2pm-1((p⌊m/2⌋-1)-⌊m/2⌋(p-1)).Theorem 9.12.
Letn=pm,m≥2 and s,l and b be defined as given in Lemma 9.11, then γ(L(Γ(ℤn[i])))=γ′(Γ(ℤn[i]))=γi′(Γ(ℤn[i]))=(s/2)+l+b if m is even and (s/2)+l+b+1 if m is odd.Proof.
Using the same notations of Lemma9.11. Note that the set S induces a complete subgraph of Γ(ℤn[i]), Ks. Thus, any edge dominating set for Γ(ℤpm×ℤpm) must contain s/2 edges to dominate Ks. If m≥3, the set L=L1∪L2 induces a complete bipartite graph Kl,l with bipartite sets L1 and L2. This contributes l edges in the dominating edge set for Γ(ℤpm×ℤpm).
Edges joining vertices inKl,l to vertices in Ks are covered by the same edge dominating sets for Kl,l and Ks. Moreover, vertices in Ak0 and A0k, where 1≤k≤m-1, are only adjacent to some vertices in Ks and Kl,l.
On the other hand, ifm≥3, the set T is an independent set. Fortunately, vertices in T are only adjacent to vertices in S. So, any edge dominating set for Ks also dominates edges between S and T.
Now, for each1≤k≤⌈m/2⌉-1, and m-k≤j≤m, the set Akj∪Ajk induces a complete bipartite graph with bipartite sets Akj and Ajk. In order to dominate this collection of complete bipartite graphs induced by Akj∪Ajk we need b edges in the edge dominating set for Γ(ℤpm×ℤpm). Fortunately, this dominating set with b elements also dominates all edges in E(Γ(ℤpm×ℤpm)) which are incident to any edge in this collection.
Finally, observe that ifm≥4, then vertices in W are only adjacent to some vertices in Ks as well as in the collection of the complete bipartite graphs. The graph Γ(ℤpm×ℤpm) has no other edges.The above proof shows thatS induces a complete graph in Γ(ℤpm×ℤpm). In fact, Ks is a complete subgraph with maximum order in case m is even, while if m is odd we can add one additional vertex of some Akj, where either k or j, say k, is ⌊m/2⌋ while j is greater than ⌊m/2⌋. On the other hand, the set T∪W∪⋃k=⌈m/2⌉m-1(Ak,0∪A0,k)∪Am,0 is a maximum independent set of order t+w+r, where r=|⋃k=⌈m/2⌉m-1(Ak,0∪A0,k)∪Am,0|=pm-1(p-1)(2p⌊m/2⌋-1).Thus, using the same notation of Lemma9.11 and the proof of the above theorem, we obtain the following corollary.Corollary 9.13.
Ifn=pm, then(i)
ω(Γ(ℤn[i]))=s if m is even and s+1 if m is odd, for m≥2,(ii)
β(L(Γ(ℤn[i])))=r, if m=2,β(L(Γ(ℤn[i])))=r+t, if m=3, and β(L(Γ(ℤn[i])))=r+t+w, for m≥3.Corollary 9.14.
Ifn=pm,m≥2, then(i)
E={v∈V(Γ(ℤn[i])):v=(u,w)whereeitheruorw∈U(ℤpm)} has eccentricity 3, while all other vertices has eccentricity 2,(ii)
the center of the graphΓ(ℤn[i]) is the set C={v∈V(Γ(ℤn[i])):v=(u,w), where both u and w∈Z(ℤpm)}-{(0,0)},(iii)
the radius of the graphΓ(ℤn[i]) equals 2,(iv)
the diameter of the graphΓ(ℤn[i]) equals 3.Proof.
(i) First, note thatΓ(ℤpm[i]) has no vertex of eccentricity 1, otherwise γ(Γ(ℤpm[i]))=1. Let u,w,α,β∈U((ℤpm)) and 1≤r,s≤m-1. If (x,y) is adjacent to both (upr,β) and (α,wpr), then x=y=0. So, d((upr,β),(α,wps))=3, and hence, the eccentricity of each vertex in E is 3. If (upr,y),(wps,x) are nonadjacent, then (pm-1,0) is adjacent to both vertices. Similarly, if (x,upr),(y,wps) are nonadjacent, then (0,pm-1) is adjacent to both vertices.



---

*Source: 957284-2012-01-27.xml*