On the Line Graph of the Zero Divisor Graph for the Ring of Gaussian Integers Modulo n

(1)

Volume 2012, Article ID 957284,13pages doi:10.1155/2012/957284

Research Article

On the Line Graph of the Zero Divisor Graph for the Ring of Gaussian Integers Modulo n

Khalida Nazzal

¹

and Manal Ghanem

²

1Department of Mathematics, Palestine Technical University-Kadoorie, P.O. Box 7 Tulkarm, West Bank, Palestine

2Department of Mathematics, Irbid National University, P.O. Box 2600 Irbid, 21110, Jordan

Correspondence should be addressed to Manal Ghanem,dr [email protected] Received 9 September 2011; Accepted 26 December 2011

Academic Editor: Gelasio Salazar

Copyrightq2012 K. Nazzal and M. Ghanem. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

LetΓZnibe the zero divisor graph for the ring of the Gaussian integers modulon. Several properties of the line graph ofΓZni,LΓZniare studied. It is determined whenLΓZni 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 ofLΓZniis given whennis a power of a prime. On the other hand, several graph invariants forΓZniare also determined.

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, Beck1defined the concept of zero divisor graph of a commutative ringR, where the vertices of this graph are all elements in the ring and two verticesx,yare adjacent if and only ifxy 0. Anderson and Livingston 2modified the definition of zero divisor graphs by restricting the vertices to the nonzero zero divisors of the ringR. Further study of zero divisor graphs by Anderson et al.3investigated several graph theoretic properties, such as the number of cliques inΓR. They also gave some cases in whichΓRis planer. On the other hand, they answered the question whenΓR1∼ ΓR₂for some specified types of ringsR1andR2. Akbari and Mohammadian4improved on those results.ΓRfor ringsR which satisfy certain conditions are discussed by Anderson and Badawi5. The zero divisor graph of the ring of integers modulonwas extensively studied in6–10.

In 2008, Abu Osba et al. 11 introduced the zero divisor graphs for the ring of Gaussian integers modulo n, ΓZni, where they studied several graph properties and

(2)

determined several graph invariants for ΓZni. Further properties of the zero divisor graphs for the ring of Gaussian integers modulonare investigated in12.

In this paper, we study the line graph ofΓZni. We organized our work as follows:

some basic definitions and terminology are given inSection 2. In Sections3and4, we answer the question when is the line graphLΓZniEulerian, Hamiltonian, or planer. InSection 5, the chromatic and clique numbers ofLΓZniare found. While the diameter, the girth and the radius ofLΓZniare determined in Sections6and7, respectively. Finally, the last two sections discuss the domination number ofΓZniandLΓZnias well as the independence and clique numbers ofΓZni.

2. Preliminaries

The set of Gaussian integers is defined byZi {abi:a, b∈Zandi√

−1}.

A prime Gaussian integer is one of the following:

i 1ior1−i,

iiq, whereqis a prime integer andq≡3mod4,

iiiabi,a−bi, wherea²b²p,pis a prime integer andp≡1mod4.

It is clear thatZniis a ring with addition and multiplications modulon. Throughout this paper,pwill be used to denote a prime integer which is congruent to 1 modulo 4, while qwill denote a prime integer which is congruent to 3 modulo 4. SinceZniis finite, each element inZniis either a zero divisor or a unit. Also, sinceZiis a unique factorization do- main, each integerncan be uniquely factorized asn_k

j1π_j^m^jwhereπ_jsare Gaussian prime integers andm_jsare positive integers.

The zero divisor graph of a commutative ringRdenoted 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ΓRandxy0}. The line graphLGof a graphGis defined to be the graph whose vertices are the edges ofG, with two vertices being adjacent if the corresponding edges share a vertex inG. ForΓZni, ifn2, then this graph is one vertex, while ifnq, thenΓZni K₀. Throughout this paper, all rings,R, are commutative with unity.

For a connected graphG, the distance,du, v, between two verticesuand vis the minimum of the lengths of allu−vpaths ofG. The eccentricity of a vertexvinGis the maximum distance fromvto any vertex inG. The radius ofG, radG, is the minimum eccentricity among the vertices ofG. The diameter ofG, diamG, is the maximum eccentricity among the vertices ofG. The girth ofG,gG, is the length of a shortest cycle inG. The center ofGis the set of all vertices ofGwith eccentricity equal to the radius. IfGhas a walk that traverses each edge exactly once goes through all vertices and ends at the starting vertex, thenGis called Eulerian. A graph is called Hamiltonian if there exists a cycle containing every vertex. The chromatic number of a graphG,χG, is the minimumksuch thatGisk-colorablei.e., can be colored usingkdiﬀerent colors such that no two adjacent vertices have the same color.

The clique number,ωG, of a graphGis the maximum order among the complete subgraphs ofG. A subsetDof the vertex setVGis said to be independent if no two vertices in this set are adjacent. The independence number ofG,βG, is the maximum cardinality of all independent sets inG. A subsetDof the vertex setVGof a graphGis a dominating set inGif each vertex ofG, not inD, is adjacent to at least one vertex ofD. The minimum cardinality of all dominating sets inG,γG, is called the domination number ofG. Edge dominating sets are defined analogously. The minimum cardinality of all edge dominating sets inG, `γG, is called the edge domination number of G. The minimum cardinality of all independent

(3)

edge dominating sets, ´γiG, is called the independence edge domination number ofG. The maximum vertex degree of a graphGwill be denoted byΔG.

3. When Is LΓZ

n

i Eulerian?

Now it is characterized when the line graphLΓZniis Eulerian. Before proceeding, we prove the following lemma.

Lemma 3.1. (i) Every vertex ofΓZnihas even degree if and only ifn2,por n is a composite in- teger which is a product of distinct odd primes.

(ii) Ifnt^m,m≥2 andn /q², thenΓZnihas a vertex of odd degree and another of even degree.

(iii) Every vertex ofΓZnihas odd degree if and only ifnq².

Proof. i Since the graph G is Eulerian if and only if each vertex has an even degree by Theorem 29 of11, the result holds.

iiAssume thatnt^m, tis prime,m≥2 andn /q². Then we have three cases.

Case It2. Then deg1i 1 and deg2^m−12^m−1i 2^2m−1−2.

Case IItis an odd prime andm >2. By Theorem 23 of11,ΓZnihas a vertex of degree t^2k−1−1, where 1≤k < m/2 and a vertex of degreet^2k−2, wherem/2≤k < m.

Case IIItpa²b²andm2. Since degaib | pa−ib|−1 and| pa−ib|divides

|Zp²|,| pa−ib|is odd and hence degaibis even. Then by using parti, the result holds.

iii ⇒Letn Π^k_j1a^m_j^j,k≥2, andx_j xt, where

xt

⎧⎨

⎩

1, iftj,

0, otherwise. 3.1

Now if all a_jsare odd primes, then degxj n/a^m_j^j−1 and if a₁ 2, then degx1

n/2^m¹−1.

⇐Note that,ΓZq²i∼K_q²₋₁. So, degv q²−2 for every vertexvinΓZq²i.

SinceLΓRis Eulerian if and only if degvis even for everyv∈ΓRor degvis odd for everyv∈ΓR,9, together with Lemma 3.1 and Theorem 26 of11, the following theorem is obtained.

Theorem 3.2. (i)LΓZniis Eulerian graph if and only ifn2, p, q², ornis a composite integer which is a product of distinct odd primes.

(ii)LΓZniis Eulerian graph does not necessarily imply thatΓZniis Eulerian.

4. When Is LΓZ

n

i Hamiltonian or Planner?

First we determine which graphs, ΓZni, are Hamiltonian. Before this paper comes to the light, a recent article by Abu Osba et al. 12 reached to similar results concerning

(4)

Hamiltonian ΓZni. However, we present our proof since it is simpler and shorter. The proof makes use of the following theorem.

Theorem 4.1see4. LetRbe a finite principal ideal ring, ifΓRis Hamiltonian, then it is either a complete graph or a complete bipartite graph.

Theorem 4.2. The graphΓZniis Hamiltonian if and only ifnporq².

Proof. SinceZniis a finite principal ideal ring,ΓZniis a complete graph or a complete bipartite graph ifΓZniis Hamiltonian. But the graphΓZniis complete if and only if n q², and it is complete bipartite if and only ifn porq₁q₂, whereq₁ < q₂,11. On the other hand, a complete bipartite graphK_m,nis Hamiltonian if and only ifmn. So the result holds.

Note thatΓZq1q2iis not Hamiltonian and hence the converse ofTheorem 4.1is not true.

Next, we move to the line graphs LΓZni. Before proceeding, we present the following theorem.

Theorem 4.3. iIf G is a graph of diameter at most 2 with|VG| ≥4, thenLGis Hamiltonian, see [13].

iiThe line graph of an Eulerian graph is both Hamiltonian and Eulerian, see [14].

Ifnp, 2^m, orq^m, wherem≥2, then diamΓZni≤2. On the other hand, ifn2, p ornis a composite odd integer which is a product of distinct primes, thenΓZniis Eulerian, 11. Thus the following corollary is obtained.

Corollary 4.4. iIfnp, 2^m, orq^m, wherem≥2, thenLΓZniis Hamiltonian.

iiIfnis a composite odd integer which is a product of distinct primes, thenLΓZniis both Eulerian and Hamiltonian.

Now, we discuss planarity of the graphLΓZni.

A graphGis planar if it can be drawn in the plane without any edge crossing. The following theorem gives necessary and suﬃcient conditions on a graphGso that the line graph LGis planer.

Theorem 4.5see15. A nonempty graphGhas a planer line graphLGif and only if

iG is planer, ii ΔG≤4,

iiiif deg_Gv 4, thenvis a cut vertex.

Recall thatΓZniis planer if and only ifn2 orn 4,11. ButLΓZ4iis not planer sinceΔΓZ4i 7>4. Therefore, we get the following theorem.

Theorem 4.6. The graphLΓZniis never planer.

(5)

5. The Chromatic and Clique Numbers of LΓZ

n

i

IfRis a finite ring, thenχΓR ΔΓR, unlessΓRis complete graph of odd order,4.

Note that, the only complete graphΓZnioccurs whenn q². However, in this case the order of the graph isq² −1 which is even, soχΓZni ΔΓZni. Moreover, since the edge coloring of any graph leads to a vertex coloring of its line graph, we obtain χLΓZni ΔΓZni. Clearly,χG ≥ ωG. On the other hand, the line graph of Ghas a complete subgraph of orderΔG. ThusωLΓZni≥ΔΓZni. Observe that ifn 2^m orq^m, m≥ 2, thenΓZnihas a vertex which is adjacent to every other vertex in ΓZni. While ifnp^m, m≥1, thenZp^mi∼Zp^m ×Zp^m. ThusΔΓZp^mi p^2m−1−1. This leads to the following theorem.

Theorem 5.1.

ωLΓZni χLΓZni

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

2^2m−1−2, ifn2^m, m≥2, q^2m−2−2, ifnq^m, m≥2, p^2m−1−1, ifnp^m, m≥1.

5.1

Finally, ifn 2^m_r

j1p^r_j^j_l

j1q_j_s

j1q^s_j^j, wheres_j ≥ 2 and m, r_j ≥ 1, then the clique number and the chromatic number for the graph LΓZni is given by the following theorem.

Theorem 5.2. n2^m_r

j1p^r_j^j_l

j1q_j_s

j1q^s_j^j, wherem, r_j ≥1 ands_j≥2, then

ωLΓZni χLΓZni

2^2m−1−1 ^r

j1

p_j^2r^j−1 ^s

j1

q^2s_j ^j⁻²−1

−1. 5.2

Proof. The result follows by computing ΔΓZni, since ΔΓZni ωLΓZni χLΓZni.

6. The Diameter of LΓZ

n

i

Now, we will find the diameter of the line graphLΓZni.

First, we will prove that diamLΓZni 2 whenn2^mornq^m.

Lemma 6.1. (i) Ifn2^m, m≥2, then there are noabi, cdi∈Zni, wherea, b, c, dare odd in- tegers such thatabicdi≡0mod4.

(ii) Ifnq^m, m≥2 then there are noabi, cdi∈Zniwherea, b, c, dare relatively prime withq, such thatabicdi≡0modq.

Proof. iAssume thatabicdi ≡ 0mod4. Then ac−bd ≡ 0mod4andadbc ≡ 0mod 4. Sincea, b, c, dare odd integers,a2a₁1,b2b₁1,c2c₁1, andd2d₁1 for somea1, b1, c1, d1∈Z. Soac−bd≡a1c1b1d1≡0mod2. Andadbc≡a1c1b1 d₁≡1mod2, a contradiction.

(6)

iiAssume thatabicdi ≡0modq. Thenac−bd≡ 0modqandadbc ≡ 0modq. Sincea, b, c, dare relatively prime withq, we havea qa₁a₂,b qb₁b₂,c qc₁c₂anddqd₁d₂, where 0< a₂, b₂, c₂, d₂< q. So

ac−bd≡a₂c₂−b₂d₂≡0 modq

, 6.1

adbc≡a₂d₂b₂c₂≡0 modq

. 6.2

Multiplying6.1byc₂and6.2byd₂and adding givesa₂c22d₂²≡0modq. Thenq|a2

orq|c22d22. Sincea2< q,q|c22d22. Therefore,c22d22≡0modq, and hencec2 ≡d2≡ 0modq, a contradiction.

So, we conclude the following.

Theorem 6.2. Ifn2^morq^mandm≥2, then diamLΓZni 2.

Proof. iSuppose thatn2^m, m≥2. Then,

1x a2^tb2^kiwherea, bare odd andt /kort k≥ m/2implies that annx {c2^rd2^si: cand dare odd andr, s≥m−min{t, k}},

2x2^tabiwherea, bare odd andt <m/2, then annx {c2^rd2^si: candd are odd andr, s≥m−t} ∪ {2^m−t−1cdi:canddare odd}.

Moreover,d2^ta1b₁i,2^m−t−1c1d₁i,2^sa2b₂i,2^m−s−1c2d₂i 2 ift≤s <

m/2. Since2^sa2b₂i,2^m−t−1c1d₁i∈VLΓZni.

iiSuppose thatn q^m, m ≥ 2. Letx aq^tbq^kianda, b ∈ UZn. Then annx {cq^r dq^si: r, s≥ m−min{t, k}}. Moreover,da1q^r¹b₁q^s¹i, c₁q^t¹d₁q^k¹i,a2q^r²b₂q^s²i, c₂q^t² d₂q^k²i 2 since r₁, s₁, t₂, k₂ ≥ m/2 implies that a1q^r¹ b₁q^s¹i, c₂q^t² d₂q^k²i ∈ VLΓZni.

From Theorems 3.1 and 3.3 of9, 2≤ diamLΓZni≤ 3. InLΓZp^mi, where pa²b²andm≥2,dp, p^m−1,aib^m,a−ib^m 3. So, diamLΓZp^mi 3.

Theorem 6.3. (i) If n st, where s, t are two distinct primes and s /p or t /p, then diamLΓZni 2.

(ii) Ifnst²are two distinct primes ands, t /p, then diamLΓZni 2.

Proof. First note that diamLΓR≥2,9and forn n1n2with g.c.dn1, n2 1,Zni ∼ Zn1i×Zn2i.

iCase I: If n qporn 2pwhere p a²b², thenVLΓZni {u, αa bi,0, βa−bi} ∪ {0, αabi,u, βa−bi} ∪ {u,0,0, v}.

Case II: Ifn2q or nq1q2, then

VLΓZni {u,0,0, v:u, v /0}. 6.3

iiNote thatVLΓZni {u, αt,0, βt} ∪ {u,0,0, v:u, v, α, β /0}.

(7)

Theorem 6.4. iIfnsp², wheresis prime andpa²b², then diamLΓZni 3.

iiIfnp^m₁p₂^l, wherep₁a²₁b²₁,p₂a²₂b²₂andm, l≥1, then diamLΓZni 3.

iii If n p^mt^l, where p a² b², m ≥ 1, l ≥ 2, and g.c.dp, t 1, then diamLΓZni 3.

ivIfns^mt^lwheres, tare distinct primes andm, l≥2, then diamLΓZni 3.

Proof. iLetv₁ 0,abi²,1,a−bi²andv₂ 0,a−biabi,1,a−biabi.

Thendv1, v2 3.

iiLetv a1b1i^m,a2b2i^l,a1−b1i^m,a2−b2i^l. Thendv,1,0,0,1 3.

iiiLetv abi^m, t,a−bi^m, t^l−1. Thendv,1,0,0,1 3.

ivLetv s, t,s^m−1, t^l−1. Thendv,1,0,0,1 3.

Theorem 6.5. (i) IfR₁, R₂, R₃are fields andRR₁×R₂×R₃, then diamLΓR 2.

(ii) IfR₁, R₂, R₃are finite rings andR_iis not a field for somei∈ {1,2,3}andRR₁×R2×R₃,

then diamLΓR 3.

(iii) IfR Π^k_i1Riwherek≥4, then diamLΓR 3.

Proof. iLeta1, a₂, a₃,b1, b₂, b₃c1, c₂, c₃,d1, d₂, d₃∈ELΓR. SinceR₁, R₂, R₃are fields,a1, a2, a3orb1, b2, b3has exactly two components equal 0. W.L.O.G. leta1, a2, a3

a1,0,0anda1/0. Sincec1d1 0,c10 ord1 0. Sayc1 0, thena1, a2, a3,c1, c2, c3∈ ELΓR. So, diamLΓR 2.

ii Suppose thatR1 is not a field. Letx, y ∈ R^∗₁ such thatxy 0. Then dx,0,1, y,1,0,0,1,1,1,0,0 3.

iiiLetx xj, wherex_j1 ifj1,2 and 0 otherwise,y yj, wherey_j 1 ifj 3,4 and 0 otherwise,z zj, wherezj 1 ifj 2,3 and 0 otherwise andw wj, where wj 1 ifj1,4 and 0 otherwise. Thendx, y,z, w 3.

Summarizing the above results, we get the following theorem.

Theorem 6.6. (i) diamLΓZni 2 if and only ifnp,2q, q₁q₂, q₁q₂q₃,2q₁q₂,4q,2q²,2p, qp orn2^m, q^mwithm≥2.

(ii) diamLΓZni 3 otherwise.

7. The Girth and the Radius of LΓZ

n

i

In this section, we give a complete characterization of the girth and the radius ofLΓZni.

Since for any commutative ringR,LΓRis a tree if and only ifΓR K2orK1,29, LΓZniis never a tree. On the other hand, ifLΓRcontains a cycle, thengLΓR≤4 where equality holds only ifRZ3×Z3,9.

Consequently, the following result holds.

Theorem 7.1. gLΓZni 3.

Next, we prove that the radius of the line graphLΓZniequals 2.

Since diamLΓR≤3,9and radG≤diamGfor any graphG, radLΓR≤3.

Lemma 7.2. If there exists a vertexv∈LΓZniwith eccentricity 2, then radLΓZni 2 Proof. Note that,LΓZnihas no spanning star graph, since ifa, b∈VΓZnisuch that a /bandab0, thenda, b,ai, bi>1.

(8)

Theorem 7.3. Ifn2^m,nq^m,m≥2 ornp^m,m≥1, then radLΓZni 2.

Proof. 1Ifn2^m, m≥2, thend2^m−12^m−1i,2,x, y≤2 for allx, y∈VLΓZni.

2Ifnq^m,m≥2, thendq^m−1, q,x, y≤2 for allx, y∈VLΓZni.

3Ifnp^m, m≥1, thendabi^ma−bi^m−1,a−bi^mabi^m−1,x, y≤2 for all x, y∈VLΓZni.

Theorem 7.4. Ifnr^mt, wherer2, q, orpandm≥1,g.c.dr, t 1, then radLΓZni 2.

Proof. 1 If r 2 or q, then dr^m−1,0,r,1,x, y,t, s ≤ 2 for all x, y,t, s ∈ VLΓZni.

2If r p a² b², then dabi^ma− bi^m−1,0, a−bi^ma bi^m−1,0, x, y,t, s≤2 for allx, y,t, s∈VLΓZni.

Summarizing the above results, we get the following.

Theorem 7.5. The radius of the line graphLΓZniequals 2.

8. The Domination Number of ΓZ

n

i

Pervious results concerning the domination number ofΓZniare very restricted; Abu Osba et al.11answered the question “when is the domination number 1 or 2?”. Here we find the domination number of the graphΓZni. Two independent proofs reflecting two diﬀerent viewpoints are given, the first proof depends on ring theory. While the second proof is con- structive in the sense that it does not only give the domination number ofΓZni, but also gives a minimum dominating set of this graph. This dominating set, as we will see, reveals to have interesting properties.

Theorem 8.1see16. LetRbe a finite commutative ring with identity that is not an integral do- main. IfΓRis not a star graph, then the domination number equals the number of distinct maximal ideals ofR.

Theorem 8.2. Ifn_k

j1π_j^m^j, wherek≥1 andπ_jsare distinct gaussian prime andm_jsare positive integers andn /2 orq. ThenγΓZni k, ifnis odd, andγΓZni k−1, ifnis even.

Proof. I 1Ifn2^m, then 1iis the unique maximal ideal ofZni.

2Ifnq^m, then qis the unique maximal ideal ofZni.

3If n p^m where p a²b², then abi and a−biare the only distinct maximal ideals ofZni.

4Ifn _k

j1π_j^m^j is odd then πj ×_k

t1,t /jZi/ π_t^m^tare the only maximal ideals ofZni.

5Ifn _k

j1π_j^m^j is even thenπ1 1i, π2 1−iand πj ×_k

t1,t /jZi/

π_t^m^twherej /2 are the only distinct maximal ideals ofZni. Finally, sinceΓZniis never a star graph11, the result holds.

(9)

Proof. IIWe have two cases.

Case I:nis odd. Then it is easy to see thatD{Pjπ₁^m¹π₂^m². . . π_j^m^j⁻¹. . . π_k^m^k : 1≤j ≤k}

is a dominating set ofΓZni. To show thatDis a minimum dominating set, assume thatD₁ is a minimum dominating set such that there is noxsP_j, g.c.ds, πj 1 belongs toD₁for some 1≤j ≤k. ThenTj {πj,2πj} ⊆D1. So,D1−Tj∪ {Pj}is a dominating set ofΓZni, a contradiction.

Case II:nis even. Thenπ₁ 1i, π2 1−i. Similar to case I, we can see thatD {Pjπ₁^m¹π₂^m². . . π_j^m^j⁻¹. . . π_k^m^k : 1≤j≤k, j /2}is a minimum dominating set ofΓZni.

If a dominating setDinduces a complete graph, then,Dis called clique dominating set, the clique domination number is the cardinality of a minimum clique dominating set, and is denoted byγ_clG, if every vertex inD is adjacent to another vertex inD, thenD is called total dominating set. The minimum cardinality of a total dominating set is called total domination number and is denoted byγtG. For any graphG,γG≤γtG≤γclG. Since the suggested dominating set,D, forΓZniin the second proof ofTheorem 8.2induces a complete graph, thenγΓZni γtΓZni γclΓZni.

9. The Domination Number of L ΓZ

n

i

In this section we determine the domination number ofLΓZniwhen n t^m and tis prime.

The study of the domination number of the line graph ofGleads to the study of edge or line domination number ofG, that is,γLG γG. On the other hand, for any graphG, γ_iG γG,17. Further, ifGis the complete bipartite graphK_r,s, thenγG minr, s, thus we have the following.

Lemma 9.1. (i)γLΓZpi γ_iΓZpi γΓZpi p−1.

(ii)γLΓZq1q2i γ_iΓZq1q2i γΓZq1q2i q₁, whereq₁< q₂.

Now, we study the domination number of the line graph ofΓZniwhennis a power of a prime. The first theorem treats the casen2^m, m≥2. Here we make use of the fact that ΓZ2^mi∼ ΓZ2^2m,12.

Theorem 9.2. Forn2^m, m≥2,

γLΓZni γ_iΓZni γΓZni 1

22^m−1

. 9.1

Proof. Forj 1,2, . . . ,2m−1, letA_j{α2^2m−j :α∈ {1,3, . . . ,2^j−1}}. Note that the setsA_jform a partition to the vertices ofΓZ2^2m. LetS_m

j1AjandT _2m−1

jm1Aj. Then the setSinduces a complete subgraph ofΓZ2^2mand the setT form an independent set of it. And each vertex inA_kis adjacent to each vertex in_2m−k

j1 A_j.ΓZ2^2mhas no other edges. LetD⊂EΓZ2^2mbe a dominating set of vertices forLΓZ2^2mwith minimum cardinality. Since, the setSinduces a complete subgraph ofΓZ2^2mof order 2^m−1, thenγLΓZ2^mi≥ 1/22^m−1. On the other hand, sinceD dominates all edges in the complete graph S,D also dominates every edge joiningStoT, recall thatT forms an independent set and soγLΓZ2^mi 1/22^m−1.

(10)

The proof ofTheorem 9.2. shows the setTis an independent set with maximum cardinality inΓZ2^mi, while the setSinduces a complete subgraph with maximum order.

So, the following corollary is obtained.

Corollary 9.3. Forn2^m, m≥2,

iωΓZni 2^m−1, iiβΓZni 2^m2^m−1−1.

As another consequence to the proof of the preceding theorem, the following corollary, which gives the degree sequence forΓZ2^mi, is obtained.

Corollary 9.4. Forj 1,2, . . . ,2m−1, the graphΓZ2^mihas exactly 2^j−1vertices of degree 2^2m−j−2 if 1≤j≤mand 2^j−1vertices of degree 2^2m−j−1 ifm1≤j ≤2m−1.

Proof. For eachv∈Aj, where 1≤j ≤m,v²0, so degv |2m−j

k1 Ak|−12^2m−j−2. And for eachv∈A_k, wherem1≤k≤2m−1,v²/0, so degv |_2m−j

k1 A_k|2^2m−j−1.

Furthermore, The proof of the above theorem shows that the eccentricity of 2^2m−1is 1 and the eccentricity of any other vertex inΓZ2^2mis 2, since the vertex 2 is adjacent only to the vertex 2^2m−1, and for anyx∈VΓZ2^mi, 2–2^2m−1–x, is a path of length 2. This leads to the following corollary.

Corollary 9.5. The center of the graphΓZ2^miis the set{2^m−11i}.

Next, we we find the domination number of the line graphLΓZniwhennq^m, m≥2.

Lemma 9.6. (i) Form≥2,

1IfAkj {aq^kbq^ji:a∈UZ_q^m−k, b∈UZ_q^m−j}, then|Akj| q−1²q^{2m−k−j−2}when 1≤k, j≤m−1,|Amj|q^m−j−q^m−j−1and|Akm|q^m−k−q^m−k−1whenk, j /m, 2IfS

m/2≤k,j≤mAkj−Amm, then|S|q^2m/2−1.

(ii) Form≥3, ifT

1≤k,j≤m/2−1A_kj, then|T|q^2m/2q^m/2−1².

Theorem 9.7. Ifnq^m, m≥2, thenγLΓZni γΓZni γ_iΓZni 1/2q^m− 1ifmis even and1/2q^2m/21ifmis odd.

Proof. LetA_kj, S, andTbe defined as given inLemma 9.6. Clearly, the setSinduces a complete subgraph ofΓZniwith maximum order ifmis even andS∪ {q^m/2}induces a complete subgraph ofΓZniwith maximum order ifmis odd. On other hand ifm≥3, thenTform an independent set with maximum cardinality. Moreover, if a vertexvbelongs to the setA_rs, thenvis adjacent to every element inAkjwherem−min{r, s} ≤k, j ≤mandk, j /mat the same time.ΓZnihas no other edges.

As a consequence of the proof ofTheorem 9.7, we conclude the following.

(11)

Corollary 9.8. Ifnq^m, m≥2, then

iωΓZni q^m−1 ifmis even andq^2m/2ifmis odd,

iiβLΓZni 1 ifm2 andβLΓZni q^2m/2q^m/2−1²ifm≥3.

Corollary 9.9. Letnq^m,m≥2, andvaq^rbq^siwherea, b∈UZn. Then

degv

⎧⎪

⎨

⎪⎩

q^{2 min{r,s}}−2, if r, s≥m 2

, q^{2 min{r,s}}−1, if r ors <m

2

. 9.2

Corollary 9.10. Letnq^m, m≥2. Then

ithe eccentricity of eachv ∈ A_m−1m−1 is 1 and the eccentricity of any other vertexv ∈ ΓZniis 2,

iithe center of the graphΓZniis the setA_m−1m−1, iiithe radius of the graphΓZniequals 1,

ivthe diameter of the graphΓZniequals 2, form≥3.

Finally, we find the domination number of the line graphLΓZniwhenn p^m, m≥2.

Recall thatZp^mi ∼ Zp^m ×Zp^m. Let,Akj {ap^k, bp^j : a ∈ UZp^m−k, b ∈ UZp^m−j}.

Clearly, the setsAkj,0 ≤k, j ≤mand not bothk, j mor 0, partition the vertices ofΓZp^m × Zp^m.

Lemma 9.11. (i) Form≥2:

1ifS

m/2≤k,j≤mA_kj−A_mm, thens|S|p^2m/2−1, 2ifL₁

0≤k≤m/2−1A_kmandL₂

0≤k≤m/2−1A_mk, thenl|L1||L2|p^m−p^m/2, (ii) form≥3:

1ifB_m/2−1

k1

_m−1

jm−kAkj, thenb|B| p^m−p^m−1m/2 −1−p^m−1−p^m/2, 2if T

0≤k,j≤m/2−1A_kj −A_0,0, then t |T| p^m−1−p^m/2² 2p−1p^2m−2 − p^2m−m/2−1,

(iii) form≥4:

IfW1 _m−1

km/2_m−k−1

j1 Akj,W2 _m−1

jm/2m−j−1

k1 Akj andW W1 ∪W2, thenw

|W|2p^m−1p^m/2−1− m/2p−1.

Theorem 9.12. Let n p^m, m ≥ 2 and s, l and b be defined as given in Lemma 9.11, then γLΓZni γΓZni γ_iΓZni s/2 lbifmis even ands/2 lb1 if m is odd.

Proof. Using the same notations ofLemma 9.11. Note that the setSinduces a complete subgraph ofΓZni,K_s. Thus, any edge dominating set forΓZp^m×Zp^mmust contains/2 edges to dominateKs. Ifm ≥ 3, the setL L1∪L2 induces a complete bipartite graphKl,lwith bipartite setsL₁andL₂. This contributesledges in the dominating edge set forΓZp^m×Zp^m.

(12)

Edges joining vertices inKl,lto vertices inKsare covered by the same edge dominating sets forK_l,landK_s. Moreover, vertices inA_k0andA_0k, where 1≤k≤m−1, are only adjacent to some vertices inK_sandK_l,l.

On the other hand, ifm≥3, the setT is an independent set. Fortunately, vertices inT are only adjacent to vertices inS. So, any edge dominating set forKsalso dominates edges betweenSandT.

Now, for each 1≤k≤ m/2 −1, andm−k≤j≤m, the setAkj∪Ajkinduces a complete bipartite graph with bipartite setsAkjandAjk. In order to dominate this collection of complete bipartite graphs induced byA_kj∪A_jkwe needbedges in the edge dominating set forΓZp^m×Zp^m. Fortunately, this dominating set withbelements also dominates all edges in EΓZp^m×Zp^mwhich are incident to any edge in this collection.

Finally, observe that ifm≥4, then vertices inW are only adjacent to some vertices in K_s as well as in the collection of the complete bipartite graphs. The graphΓZp^m ×Zp^mhas no other edges.

The above proof shows thatSinduces a complete graph inΓZp^m×Zp^m. In fact,Ksis a complete subgraph with maximum order in casemis even, while ifmis odd we can add one additional vertex of some Akj, where eitherk or j, sayk, ism/2whilej is greater than m/2. On the other hand, the setT ∪W∪_m−1

km/2Ak,0∪A0,k∪Am,0 is a maximum independent set of ordertwr, wherer|_m−1

km/2Ak,0∪A_0,k∪Am,0|p^m−1p−12p^m/2−1.

Thus, using the same notation ofLemma 9.11and the proof of the above theorem, we obtain the following corollary.

Corollary 9.13. Ifnp^m, then

iωΓZni sifmis even ands1 if m is odd, form≥2,

iiβLΓZni r, ifm 2, βLΓZni rt, ifm 3, andβLΓZni rtw, form≥3.

Corollary 9.14. Ifnp^m, m≥2, then

iE {v∈VΓZni: v u, wwhere either uorw ∈ UZp^m}has eccentricity 3, while all other vertices has eccentricity 2,

iithe center of the graphΓZniis the setC{v∈VΓZni:v u, w, where both uandw ∈ZZp^m} − {0,0},

iiithe radius of the graphΓZniequals 2, ivthe diameter of the graphΓZniequals 3.

Proof. iFirst, note thatΓZp^mihas no vertex of eccentricity 1, otherwiseγΓZp^mi 1.

Letu, w, α, β∈UZp^mand 1≤r, s≤m−1. Ifx, yis adjacent to bothup^r, βandα, wp^r, thenxy0. So,dup^r, β,α, wp^s 3, and hence, the eccentricity of each vertex inEis 3.

Ifup^r, y,wp^s, xare nonadjacent, then p^m−1,0is adjacent to both vertices. Similarly, if x, up^r,y, wp^sare nonadjacent, then0, p^m−1is adjacent to both vertices.

References

1 I. Beck, “Coloring of commutative rings,” Journal of Algebra, vol. 116, no. 1, pp. 208–226, 1988.

2 D. F. Anderson and P. S. Livingston, “The zero-divisor graph of a commutative ring,” Journal of Alge- bra, vol. 217, no. 2, pp. 434–447, 1999.

(13)

3 D. F. Anderson, A. Frazier, A. Lauve, and P. S. Livingston, “The zero-divisor graph of a commutative ring. II,” in Ideal Theoretic Methods in Commutative Algebra, vol. 220 of Lecture Notes in Pure and Applied Mathematics, pp. 61–72, Marcel Dekker, New York, NY, USA, 2001.

4 S. Akbari and A. Mohammadian, “On the zero-divisor graph of a commutative ring,” Journal of Ał- gebra, vol. 274, no. 2, pp. 847–855, 2004.

5 D. F. Anderson and A. Badawi, “On the zero-divisor graph of a ring,” Communications in Algebra, vol.

36, no. 8, pp. 3073–3092, 2008.

6 N. Cordova, C. Gholston, and H. Hauser, The Structure of Zero-Divisor Graphs, Summer Undergraduate Mathematical Sciences Research Institute, Miami University, 2005.

7 A. Duane, “Proper Coloring and p-partite structures of the zero-divisor graph,” Rose-Hulman Undergraduate Mathematics Journal, vol. 7, no. 2, pp. 1–7, 2006.

8 V. K. Bhat, R. Raina, N. Nehra, and O. Prakash, “A note on zero divisor graph over rings,” International Journal of Contemporary Mathematical Sciences, vol. 2, no. 13–16, pp. 667–671, 2007.

9 P. F. Lee, Line graph of zero divisor graph in commutative rings, M.S. thesis, Colorado Christian University, 2007.

10 A. Phillips, J. Rogrers, K. Tolliver, and F. Worek, Uncharted Territory of Zero-Divisor Graphs and Their Complements, Summer Undergraduate Mathematical Science Research Institute, Miami University, 2004.

11 E. Abu Osba, S. Al-Addasi, and N. Abu Jaradeh, “Zero divisor graph for the ring of Gaussian integers modulo n,” Communications in Algebra, vol. 36, no. 10, pp. 3865–3877, 2008.

12 E. Abu Osba, S. Al-Addasi, and B. Al-Khamaiseh, “Some properties of the zero-divisor graph for the ring of Gaussian integers modulo n,” Glasgow Mathematical Journal, vol. 53, no. 2, pp. 391–399, 2011.

13 H. J. Veldman, “A result on Hamiltonian line graphs involving restrictions on induced subgraphs,”

Journal of Graph Theory, vol. 12, no. 3, pp. 413–420, 1988.

14 S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addi- son-Wesley, Redwood City, Calif, USA, 1990.

15 J. Sedl´aˇcek, “Some properties of interchange graphs,” in Theory of Graphs and its Application, pp. 145–

150, Academic Press, New York, NY, USA, 1962.

16 S. P. Redmond, “Central sets and radii of the zero-divisor graphs of commutative rings,” Communica- tions in Algebra, vol. 34, no. 7, pp. 2389–2401, 2006.

17 S. Arumugam and S. Velammal, “Edge domination in graphs,” Taiwanese Journal of Mathematics, vol.

2, no. 2, pp. 173–179, 1998.

(14)

Submit your manuscripts at http://www.hindawi.com

Hindawi Publishing Corporation

http://www.hindawi.com Volume 2014

Mathematics

^{Journal of}

in Engineering

Hindawi Publishing Corporation http://www.hindawi.com

Differential Equations

International Journal of

Volume 2014

Applied Mathematics^{Journal of}

Probability and Statistics

Journal of

Mathematical PhysicsAdvances in

Complex Analysis

^{Journal of}

Optimization

^{Journal of}

Combinatorics

Operations Research

Journal of

Function Spaces

Abstract and Applied Analysis

International Journal of Mathematics and Mathematical Sciences

The Scientific World Journal

Algebra

Discrete Dynamics in Nature and Society

Decision Sciences

Discrete Mathematics

^{Journal of}

On the Line Graph of the Zero Divisor Graph for the Ring of Gaussian Integers Modulo n

Research Article