On Domination and Energy of Zero Divisor Graphs

Download Full-Text PDF Cite this Publication

Text Only Version

On Domination and Energy of Zero Divisor Graphs

K. Ananthi Department of Mathematics VSA Group of Institutions

Salem, India 636 010.

Dr. J. Ravi Sankar School of Advanced Sciences

VIT University Vellore, India 632 014.

Dr. N. Selvi Department of Mathematics

ADM College for Women, Nagapattinam, India-611001

Abstract The energy E (G) of a graph G is the sum of the absolute values of the eigenvalues of G. In this paper, we study the characterization of eigenvalues and energy of adjacency matrix corresponding to zero-divisor graphs of finite commutative ring. Also, we study the eigenvalue and energy of

Zn where n=2p, 3p, 5p, pq, p2, 4p where p, q are distinct

prime numbers. Finally, we give the relationship between the domination number, energy, rank and eigenvalues of complete zero-divisor graphs.

Keywords Commutative ring, Zero-divisor graph, Energy graph.

I. INTRODUCTION

The energy E(G), of a graph G is defined to be the sum of the absolute values of its eigenvalues. Hence, if A(G) is the adjacency matrix of G, and { 1 ,2 ,3…n } are the

The concept of energy has been generalized in two different directions. Let A be an m×n matrix and A* denote its adjoint(conjugate transpose of A).The singular values s1(A) s2(A) sm(A) of a matrix A are the square roots of the eigenvalues of AA*.Note that if A is an n×nHermitian matrix(i.e , A = A*) , then the singular values of A are the absolute values of the eigenvalues of A.For any

m

m

AMm,ndefine the energy of A , E(A) = si ( A) .From

i1

the above, we note that the usual energy of a graphG , E(G) = E(A(G)).

Another generalization of energy is defined as follows:Let Mbe a matrix associated with G. Suppose µ1,

µ2,µn are the eigenvalues of M and is the average of µ1,

µ2,µn.The M energy of G is then defined as the absolute

n

n

n

eigenvalues of A(G), then E(G)= i

i1

. The set

deviation EM(G)= i

i1

  • .If M is the adjacency matrix

{ , ,…,

} is the spectrum of G and denoted by Spec G.

A(G), then =0.Hence, the usual energy E(G) = EA(G).For

1 2 n

The totally disconnected graph

K c has zero energy while the

notation and zero-divisor graph terminology, we in general follow [4,5,6,7].

n

n

complete graph Kn with the maximum possible number of edges (among graphs on n vertices) has energy 2(n-1).Graphs for which the energy is greater than 2(n-1) are called hyperenergetic graphs. If 2(n-1), then G is called non-hyperenergetic.

The energy of G was first defined by I. Gutman in 1978 as the sum of the absolute values of the eigenvalues of A(G) in [2]. Energy of graph originated from theoretical chemistry. Huckel molecular orbital theory is a field of theoretical chemistry where graph eigen values occur. The carbon atoms of a hydrocarbon system correspond to vertices of a graph associated with the molecule. From Huckel theory, the energy of a molecular graph is equal to the – electron energy of a conjugated hydrocarbon [3].

Let R be a commutative ring and let Z(R) be its set of zero-divisors. The zero-divisor graph of a ring is the graph (simple) whose vertex set is the set of non-zero zero-divisors, and an edge is drawn between two distinct vertices if their product is zero. Throughout this paperff, we consider the

commutative ring by R and zero-divisor graph Rby

Zn . The idea of a zero-divisor graph of a commutative

ring was introduced by I.Beck in [1], where he was mainly interested in colourings. The zero-divisor graph is very useful to find the algebraic structures and properties of rings.

Claude Berge introduced the theory of Domination in 1958. The inspiration for this concept was drawn from the classical problem of covering chessboard with minimum number of chess pieces.

The most common definition given of a dominating set is that it is a set of vertices D V in a graph G = (V, E )

Theorem 2: For any graph Z , where p is any prime

3 p

3 p

3 p

3 p

having the property that every vertex v V-D is adjacent to

number, then the Eigenvalues are 2p 1,

2p 1

atleast one vertex in D . The domination number (G) is the cardinality of a smallest dominating set of G.

and EZ 2 2( p 1) .

Throughout this paper G will denote a simple (no loops or multiple edges), undirected graph with n vertices and m edges. If {v1, v2, vn} is the set of vertices of G , then the adjacency matrix of G, A(G) = A = [aij] is an n × n matrix, where aij= 1 if vi and vj are adjacent and aij= 0 otherwise. Thus, A is a symmetric (0, 1) matrix with real eigenvalues and zeros on the diagonal. If 1 , 2 ,…n are the eigenvalues of A, then we

have 1 2 … n and 1 2 …n 0 .

Proof: The vertex set of Z is {3,6,9,3(p-1),p,2p}. Let u and v be two vertices in Z with maximum degree.

3 p

3 p

3 p

3 p

3 p

3 p

Let u=p and v=2p then there exist any other vertex wp2p in Z such that,is adjacent to both u and v. That is, uw

=vw= 0. But uv=2p2 which is not divided by 3p. Therefore u and v are non-adjacent vertices. Then the vertex set V can be partitioned into two parts V1 and V2 such that V1={u,v}={p,2p} and V2={3,6,9,,3(p-1)}. Clearly |V1|=2 and |V2|=p-1, then

II EIGENVALUES & ENERGY OF ZERO DIVISOR GRAPHS

|V|=|V1|+|V2|=p+1.

Case(i): Let p=5.The eigenvalues of

(Z15 ) are

In this paper, we evaluate the eigenvalues of zero-divisor

graph and find the energy of some generalized zero divisor 8 , 8 .Then the energy of

graphs.

(Z15 )= Sum of the

2 p

2 p

Theorem1: For any graph Z , where p is any prime

absolute values of the eigenvalues= 8

8 2 8 .

number, then the eigenvalues are

p 1,

p 1 and

Case (ii): Let p=7.The Eigenvalues of

(Z21) are

2 p

2 p

EZ

2

12,

12

. Then the energy of

(Z21) = Sum

of

the

absolute

values

of

the

12,

12

. Then the energy of

(Z21) = Sum

of

the

absolute

values

of

the

p 1 .

Proof: The vertex set of Z 2 p is {2, 4, 6 2(p-1), p}. Let

Eigenvalues= 12 12 12 .

u=4 and v=p then 2p must divides uv. That is 2p divides 4p.

Clearly, u and v are adjacent vertices. Similarly, any vertices

Case(iii):Let p>7, is a prime number.

2 p

2 p

u in V Z and v=p then 2p must divides uv. It seems

In general, the eigenvalues of

Z3 p are

2 p

2 p

that p is adjacent to all the vertices in V Z

.Let u=4p

2( p 1), 2( p 1). Then the energy of

Z =

3 p

3 p

and

Sum of the absolute values of the

2 p

2 p

2 p

2 p

5 p

5 p

w=6p in V Z such that uw 0 It means that 2p does

eigenvalues= 2( p 1) 2( p 1) 2 2( p 1).

not divide uv=24. Clearly, no two vertices in

Z

are

Theorem 3: For any graph Z ,where p is any prime

adjacent, except p.

Case(i): Let p=3.The eigenvalues of

Z6

number, then the eigenvalues are

are 2 ,- 2 .

4p 1,

4p 1

Then the energy of Z6

=Sum of the absolute values of

and EZ5 p 2 4( p 1) .

the eigenvalues= 2

2 2 2.

Proof: The vertex set of

(Z5 p )

is {5,10, . . .5(p-1), p,

Case(ii): Let p=5.The eigenvalues of

Z

are 4 ,- 4 .

2p,3p,4p}. Clearly V ((Z5 p )) p 3 .Let u and v be any

Then the energy of Z10

10

=Sum of the absolute values of

two vertices in (Z5 p ) with maximum and minimum

the eigenvalues= 4

4 4.

degree, respectively. Let u = p and v=10 then 5p must divide uv which implies that u and v are adjacent.

Case (iii): Let p>5, is a prime number.

In general, the eigenvalues of

2 p

2 p

p 1, p 1 . Then the energy of Z

Z are

2 p

2 p

=Sum of the

Let u=p and v=2p then 5p does not divide uv=2p2, which implies that u and v are non adjacent vertices. Then the vertex set V can be partitioned into two parts V1 and V2, where V1={p,2p,3p,4p} and V2= {5,10,,5(p-1)}.Clearly

absolute values of the

any vertices u and v in V1are non-adjacent as same as in V2.

eigenvalues=

p 1

p 1 2

p 1 .

Let u=p in V1 and v=10 are in V2 then 5p divides uv=10p. Finally, we note that, every vertex in V1 is adjacent to all the

vertices

V Z5 p

in V2.Moreover

V1 V2 and V1 V2 .

Case(i):Let p=7.The eigenvalues of (Z35 ) are

( p 1)(q 1), ( p 1)(q 1) and

24, 24 .Then the energy of (Z35 ) = Sum of the

EZ pq 2 ( p 1)(q 1) .

absolute values of the eigenvalues= 24 24 2 24 .

Proof: The proof is by the method of induction on p and q. The vertex set of Z is {p,2p,3p,,p(q-

pq

pq

Case(ii):Let p=11.The eigenvalues of (Z55 ) are

1),q,2q,3q,,(p-1)q}.

2q

2q

Case(i): Let p=2,q is any prime>2,Using theorem (2.1), for

40 , 40 .Then the energy of (Z55 ) = Sum of the

any graph Z , where q>2 is any prime number, then the

absolute values of the

eigenvalues= 40 40 2 40 .

eigenvalues are q 1 , q 1 .Without loss of generality, the eigenvalues can be written as

Case (iii): Let p>11 , is a prime number.In general, the

( p 1)(q 1) ,

( p 1)(q 1) , where p=2.

eigenvalues of

Z

are

5 p

5 p

4( p 1),

4( p 1) . Then

Then, EZ 2q 2

(q 1) 2

(2 1)(q 1) 2

( p 1)(q 1),

the energy of

Z5 p =Sum of the absolute values of the

where p=2.

Case(ii): Let p=3,q is any prime>3,Using theorem (2.2), for

p

p

Eigenvalues= 4( p 1) 4( p 1) 2

4( p 1) .

any graph Z , where q>3 is any prime number, then the

Theorem 4: For any graph Z

2 , where p>2 is any prime

3q

eigenvalues are 2(q 1), 2(q 1) . Without loss of

number, then the eigenvalues are

1,1,… 1, ( p 2) and

generality, the eigenvalues can be written as

( p2)times

( p 1)(q 1) , ( p 1)(q 1) ,where p=3.

E Z 2 2( p 2) .

Then,

p

E Z3q

2 2(q 1) 2

(3 1)(q 1) 2

( p 1)(q 1),

Proof: If p is any prime, then

p

p

V Z 2 ={p,2p,3p,4p,,(p-1)p}. Clearly p is adjacent to

where p=3.

5q

5q

p

p

all the vertices in Z 2

. Also note that, any two vertices

p

p

Case(iii):Let p =5,q is any prime>5,Using theorem (2.3), for any graph Z , where q>5 is any prime number, then the

p

p

in Z 2

is adjacent and hence

Z 2

is a complete

eigenvalues are

4(q 1),

4(q 1) . Without loss of

graph, namely K p1 .

generality, the eigenvalues can be written as

3

3

Case(i): Let p=3.The eigenvalues of Z 2 are -1,1. Then

( p 1)(q 1), ( p 1)(q 1) ,where p=4. Then,

3

3

the energy of Z 2 =Sum of the absolute values of the

eigenvalues=2.

EZ5q 2 4(q 1) 2 (5 1)(q 1) 2 ( p 1)(q 1),

5

5

Case(ii): Let p=5.The eigenvalues of

Z 2 are -1,-1,-1,3.

where p=5.

Case(iv): Let p<q,The vertex set of

Z , is

pq

pq

5

5

Then the energy of the eigenvalues=6.

Z 2 =Sum of the absolute values of

pq

pq

pq

pq

{p,2p,3p,,p(q-1),q,2q,3q,,(p-1)q}.Using theabove cases, the eigenvalues of

7

7

Case(iii): Let p=7.The eigenvalues of Z 2 are -1,-1,-1,-1-

1,5. Then the energy of Z 2 =Sum of the absolute values

Z

are

( p 1)(q 1),

( p 1)(q 1)

where p and q

7 are distinct primes with p<q. Then the energy of

Z pq is

of the eigenvalues=10.

Case(iv): Let p>7, is a prime number.The eigenvalues of

EZ pq

( p

1)(q

1)

( p

1)(q

1) 2

( p

1)(q

1)

p

p

Z 2

are 1,1,…,1, ( p 2) .

( p2) times

.

Theorem6:If p > 4 is any prime, thenthe eigenvalues are

Then the energy of

Z

2 = Sum of the absolute values of

in the form of x, 2.4142x,where x and 2.4142x are less

p

p

the

than p and E((z4 p )) 2(x 2.4142x) .

eigenvalues=

eigenvalues=

1,… 1 ( p 2)times

1,… 1 ( p 2)times

p 2 2 p 2 .

p 2 2 p 2 .

pq

pq

Theorem5: In Z

, if p and q are distinct prime numbers

Proof: The vertex of

(Z4 p )

is {2,4, , 2(2p-1),p,2p,3p}

with p<q, then the eigenvalues are

with

V ((Z4P

2 p 1.Let v = 2p be a vertex and let w

be any vertex except p and 3p such that 4p divides vw.

G

((Zn )

E((Zn )

((Zn )

Eigenvalues

(Z6 )

1

2

2

-1,1

(Z25 )

1

6

4

-1,-1,-1,3

(Z49 )

1

10

6

-1,-1,-1,-1,-

1,5

(Z121)

1

18

10

-1,-1,-1,-1,-

1-1,-1,-1,-

1,9,

..

(Z 2 )

P

1

2p -4

p-1

1,1,… 1,(P 2)

( p2) times

G

((Zn )

E((Zn )

((Zn )

Eigenvalues

(Z6 )

1

2

2

-1,1

(Z25 )

1

6

4

-1,-1,-1,3

(Z49 )

1

10

6

-1,-1,-1,-1,-

1,5

(Z121)

1

18

10

-1,-1,-1,-1,-

1-1,-1,-1,-

1,9,

..

(Z 2 )

P

1

2p -4

p-1

1,1,… 1,(P 2)

( p2) times

Clearly, v is adjacent to all the vertices in

V ((Z4P )) expect p and 3p. Let P, S,N(S) be the pendant

set, minimum degree set, neighborhood of S, respectively. Since v has maximum degree then vN(S).

Case(i): Let p = 5.The vertex set of

(Z

20 ) is {2,4,2(10-

1),5,10,15} with

V ((Z

20 11. Let v =2p = 10 be a

vertex and letw be any vertex except 5 and 15 such that 20 divides vw. Clearly, v = 10 is adjacent to all the vertices in V ((Z20 )) except 5 and 15 then 10N(S).Let x = 2 and y

= 14 then 28 is not divisible by 20 which implies x and y are non adjacent vertices. But xv = yv = 0.

The eigenvalues of (Z20 ) are -3.6955, -1.5307, 0, 1.5307,

3.6955. Then the energy of

(Z20 ) = Sum of the absolute

values of the eigenvalues = 2(1.5307+3.6955) = 2(1.5307+2.4142(1.5307)) = 10.4524.

Case(ii): Let p = 7.The vertex set of (Z28 ) is {2,4,2(14- 1), 7,14,21} with V ( (Z28 2 p 1 15.Let v = 2p

=14 be a vertex and let w be any vertex except 7 and 21 such

that 28 divides vw. Clearly v =14 is adjacent to all the vertices in V ((Z28 )) except 7 and 21 then 14 N(S). The eigenvalues of V ((Z28 )) are -4.5261, -1.8748, 0, 1.8748, 4.5261. Then the energy of V ((Z28 )) = Sum of the absolute values of the eigenvalues = 2(1.8748+4.5261) = 2(1.8748+2.4142(1.8748)) = 12.8018

Case(iii): Let p>7is a prime numberThe vertex set of

V ((Z4 p )) is{2,4,2(2p-1),p,2p,3p}with

III CONCLUSION

In this paper, we study the eigenvalues and energy of zero divisor graph over finite commutative rings. Graphs are the most ubiquitous models of both natural and human made structures. In computer science, zero divisor graphs are used to represent networks of communication, network flow, clique problems. For any graph (Z4P ) , where p > 3 is any prime number and 4 <x< 4+x, then the eigenvalues are x , 2.4142x, approximately, where x is a position of consecutive prime number from 5 to so on.

If an Eigen value of a zero divisor graph is a rational number, then it is an integer. Also we note that the energy of a zero divisor graph cannot be an odd integer. The energy of a zero divisor graph cannot be the square root of an oddinteger.The energy of a zero divisor graph cannot be the square root of the double of an odd integer.

V ( (Z4 p )) 2 p 1 .Let v =2p be a vertex and let w be

any other vertex except p and 3p such that 4p divides vw. Clearly , v is adjacent to all the vertices V ((Z4P )) except p and 3p and v = 2p N(S).

REFERENCES

  1. I.Beck, Colouring of Commutative Rings, J. Algebra, 116,(1988),208- 226

    The eigenvalues of

    V ((Z4P ))

    are -x, -2.4142x, 0,

  2. I.Gutman,The Energy of a Graph,Ber.Math Statist.Sekt.Forschungsz.Graz,103,(1978), 1-22.

    2.4142x, x. Then the energy of V ((Z28 )) = Sum of the absolute values of the eigenvalues =2(x+2.4142x)=6.8284x.

    III Relationship between domination, energy, rank and eigenvalues of (Zn ) In this section, we find the bounds which relate the domination number of (Zn ) , energy of

    (Zn ), rank of (Zn ) and eigenvalues of (Zn ) ,for n = p2, where p >2 is any prime number.

  3. I.Gutman,O.Polanski, Mathematical Concepts in Organic Chemistry, Springer, Berlin(1986).[4]J. Ravi Sankar and S.Meena, Changing and Unchanging the Domination Number of a Commutative ring, International Journal of Algebra,6 ,(2012), No -27,1343 1352.

  4. J.Ravi Sankar and S.Meena, Connected Domination number of a commutative ring, International Journal of Mathematical Research,5,(2012), No -1, 5-11.

  5. J. Ravi Sankar,S.Sangeetha, R.Vasanthakumari and S.Meena, Crossing Number of a Zero Divisor Graph, International Journal of Algebra,6

    ,(2012), No -32,1499 1505.

  6. J.RaviSankar and S.Meena,On Weak Domination in a Zero Divisor Graph, International Journal of Applied Mathematics, 26,(2013),No 1, 83 91.

Leave a Reply

Your email address will not be published. Required fields are marked *