ON SOME INEQUALITIES FOR THE SKEW LAPLACIAN ENERGY OF DIGRAPHS

(1)

Skew Laplacian Energy of Digraphs C. Adiga and Z. Khoshbakht vol. 10, iss. 3, art. 80, 2009

Title Page

Contents

JJ II

J I

Page1of 12 Go Back Full Screen

Close

ON SOME INEQUALITIES FOR THE SKEW LAPLACIAN ENERGY OF DIGRAPHS

C. ADIGA AND Z. KHOSHBAKHT

Department of Studies in Mathematics University of Mysore

Manasagangothri

MYSORE - 570 006, INDIA

EMail:[email protected] [email protected]

Received: 16 April, 2009

Accepted: 28 July, 2009

Communicated by: S.S. Dragomir 2000 AMS Sub. Class.: 05C50, 05C90.

Key words: Digraphs, skew energy, skew Laplacian energy.

Abstract: In this paper we introduce and investigate the skew Laplacian energy of a digraph.

We establish upper and lower bounds for the skew Laplacian energy of a digraph.

Acknowledgements: We thank the referee for helpful remarks and useful suggestions. The first author is thankful to the Department of Science and Technology, Government of India, New Delhi for the financial support under the grant DST/SR/S4/MS: 490/07.

(2)

Title Page Contents

JJ II

J I

Close

1. Introduction

In this paper we are concerned with simple directed graphs. A directed graph (or just digraph)Gconsists of a non-empty finite setV(G) = {v₁, v₂, . . . , v_n}of elements called vertices and a finite setΓ(G)of ordered pairs of distinct vertices called arcs.

Two vertices are called adjacent if they are connected by an arc. The skew-adjacency matrix of G is then×n matrix S(G) = [aij]where aij = 1 whenever(vi, vj) ∈ Γ(G), a_ij = −1 whenever (v_j, v_i) ∈ Γ(G), a_ij = 0 otherwise. Hence S(G) is a skew symmetric matrix of ordern and all its eigenvalues are of the formiλ where i= √

−1andλ ∈R. The skew energy ofGis the sum of the absolute value of the eigenvalues ofS(G). For additional information on the skew energy of digraphs we refer to [1]. The degree of a vertex in a digraphGis the degree of the corresponding vertex of the underlying graph ofG. LetD(G) = diag(d₁, d₂, . . . , d_n), the diagonal matrix with vertex degreesd₁, d₂, . . . , d_n ofv₁, v₂, . . . , v_n. Then L(G) = D(G)− S(G) is called the Laplacian matrix of the digraph G. Let µ₁, µ₂, . . . , µ_n be the eigenvalues of L(G). Then the setσ_SL(G) = {µ₁, µ₂, . . . , µ_n} is called the skew Laplacian spectrum of the digraphG. The Laplacian matrix of a simple, undirected (n, m)graphG₁ isL(G₁) =D(G₁)−A(G₁),whereA(G₁)is the adjacency matrix of G1. It is symmetric, singular, positive semi-definite and all its eigenvalues are real and non negative. It is well known that the smallest eigenvalue is zero and its multiplicity is equal to the number of connected components ofG₁. The Laplacian spectrum of the graphG₁, consisting of the numbersα₁, α₂, . . . , α_nis the spectrum of its Laplacian matrixL(G₁)[3,4]. The spectrum of the graphG₁, consisting of the numbersλ₁, λ₂, . . . , λ_nis the spectrum of its adjacency matrixA(G₁). The ordinary and Laplacian eigenvalues obey the following well-known relations:

(1.1)

n

X

i=1

λ_i = 0;

n

X

i=1

λ²_i = 2m,

(4)

Title Page Contents

JJ II

J I

Close

(1.2)

n

X

i=1

α_i = 2m;

n

X

i=1

α²_i = 2m+

n

X

i=1

d²_i.

The energy of the graphG₁is defined as E(G₁) =

n

X

i=1

|λ_i|.

For a survey of the mathematical properties of the energy we refer to [5]. In order to define the Laplacian energy of G₁, Gutman and Zhou [6] introduced auxiliary

"eigenvalues"βi,i= 1,2, . . . , n, defined by β_i =α_i− 2m

n . Then it follows that

n

X

i=1

β_i = 0 and

n

X

i=1

β_i² = 2M whereM =m+¹₂Pn

i=1(d_i−^2m_n )².

If G₁ is an(n, m)-graph and its Laplacian eigenvalues are α₁, α₂, . . . , α_n, then the Laplacian energy ofG₁[6] is defined by

LE(G₁) =

n

X

i=1

|β_i|=

n

X

i=1

α_i− 2m n

.

Gutman and Zhou [6] have shown a great deal of analogy between the properties of E(G₁)andLE(G₁). Among others they proved the following two inequalities:

(1.3) LE(G1)≤√

2M n

(5)

Title Page Contents

JJ II

J I

Close

and

(1.4) 2√

M ≤LE(G₁)≤2M.

Various bounds for the Laplacian energy of a graph can be found in [8,9].

The main purpose of this paper is to introduce the concept of the skew Laplacian energySLE(G)of a simple, connected digraphG, and to establish upper and lower bounds forSLE(G)which are similar to(1.3)and(1.4). We may mention here that the skew Laplacian energy of a digraph considered in [2] was actually the second spectral moment.

(6)

Title Page Contents

JJ II

J I

Close

2. Bounds for the Skew Laplacian Energy of a Digraph

We begin by giving the formal definition of the skew Laplacian energy of a digraph.

Definition 2.1. LetS(G)be the skew adjacency matrix of a simple digraphG, pos- sessingnvertices andmedges. Then the skew Laplacian energy of the digraphGis defined as

SLE(G) =

n

X

i=1

µ_i− 2m n

,

whereµ1, µ2, . . . , µn are the eigenvalues of the Laplacian matrixL(G) = D(G)− S(G).

In analogy with (1.2), Adiga and Smitha [2] have proved that (2.1)

n

X

i=1

µ_i =

n

X

i=1

d_i = 2m

and (2.2)

n

X

i=1

µ²_i =

n

X

i=1

d_i(d_i−1).

We may observe that equations (2.1) and (2.2) are evident as (1.1) and (1.2), which follow from the trace equality.

Defineγ_i =µ_i− ^2m_n fori= 1,2, . . . , n. On using (2.1) and (2.2) we see that (2.3)

n

X

i=1

γ_i = 0

(7)

Title Page Contents

JJ II

J I

Close

and (2.4)

n

X

i=1

γ_i² = 2M, where

M =−m+1 2

n

X

i=1

d_i− 2m n

2

.

Since2m/nis the average vertex degree, we haveM +m = 0 if and only ifGis regular.

Theorem 2.2. LetGbe an(n, m)-digraph and letdi be the degree of thei^thvertex ofG, i = 1,2, . . . , n. Ifµ1, µ2, . . . , µnare the eigenvalues of the Laplacian matrix L(G) = D(G)−S(G), whereD(G) = diag(d₁, d₂, . . . , d_n)is the diagonal matrix andS(G) = [a_ij]is the skew-adjacency matrix ofG, then

SLE(G)≤p 2M₁n.

HereM₁ =M + 2m =m+¹₂Pn

i=1(d_i−^2m_n )². Proof. From(2.1)it is clear that

(2.5)

n

X

i=1

Re(µ_i) =

n

X

i=1

d_i.

By Schur’s unitary triangularization theorem, there is a unitary matrixU such that U^∗L(G)U =T = [t_ij], whereT is an upper triangular matrix with diagonal entries t_ii = µ_i, i = 1,2, . . . , n, i.e. L(G) = [s_ij]and T = [t_ij]are unitarily equivalent.

That is,

n

X

i,j=1

|s_ij|² =

n

X

i,j=1

|t_ij|² ≥

n

X

i=1

|t_ii|² =

n

X

i=1

|µ_i|².

(8)

Title Page Contents

JJ II

J I

Close

Thus (2.6)

n

X

i=1

d²_i + 2m≥

n

X

i=1

|µ_i|².

Letγ_i =µ_i−^2m_n ,i= 1,2, . . . , n. By the Cauchy-Schwarz inequality applied to the Euclidean vectors(|γ₁|,|γ₂|, . . . ,|γ_n|)and(1,1, . . . ,1), we have

(2.7) SLE(G) =

n

X

i=1

µ_i− 2m n

=

n

X

i=1

|γ_i| ≤ v u u t

n

X

i=1

|γ_i|²√ n.

Now by(2.5)and(2.6),

n

X

i=1

|γ_i|² =

n

X

i=1

µ_i− 2m n

=

n

X

i=1

|µ_i|²− 2m n

n

X

i=1

2 Reµ_i+4m² n

≤2m+

n

X

i=1

d²_i − 4m n

n

X

i=1

d_i+4m² n

= 2M₁. (2.8)

Using(2.8)in(2.7), we conclude that

SLE(G)≤p 2M₁n.

(9)

Title Page Contents

JJ II

J I

Close

Second Proof. Consider the sum

S =

n

X

i=1 n

X

j=1

(|γ_i| − |γ_j|)².

By direct calculation

S = 2n

n

X

i=1

|γ_i|²−2

n

X

i=1

|γ_i|

n

X

j=1

|γ_j|

! .

It follows from(2.8)and the definition ofSLE(G)that S ≤4nM₁−2SLE(G)². SinceS ≥0, we haveSLE(G)≤√

2M₁n.

IfE(G₁)is the ordinary energy of a simple graphG₁ it is well-known [7] that

(2.9) E(G₁)≤ 2m

n + v u u

t(n−1)

"

2m− 2m

n 2#

.

We prove an inequality similar to (2.9) involving the skew Laplacian energy of a digraph. LetGbe an(n, m)-digraph. Supposeµ₁, µ₂, . . . , µ_nare the eigenvalues of the Laplacian matrixL(G)with|γ₁| ≤ |γ₂| ≤ · · · ≤ |γ_n| =k,whereγ_i =µ_i− ^2m_n , i= 1,2, . . . , n. LetX = (|γ₁| ≤ |γ₂| ≤ · · · ≤ |γn−1|)andY = (1,1, . . . ,1). By the Cauchy-Schwarz inequality we have

n−1

X

i=1

|γi|

!2

≤(n−1)

n−1

X

i=1

|γi|².

(10)

Title Page Contents

JJ II

J I

Close

That is,

(SLE(G)− |γ_n|)² ≤(n−1)

n

X

i=1

|γ_i|²− |γ_n|²

! .

Using(2.8)in the above inequality we obtain SLE(G)≤k+p

(n−1)(2M₁ −k²), wherek =|γ_n|andM₁is as in Theorem2.2.

Theorem 2.3. We have

2p

|M| ≤SLE(G)≤2M1.

Proof. SincePn

i=1γ_i = 0, we have

n

X

i=1

γ_i² + 2

n

X

i<j

γ_iγ_j = 0.

Now, using(2.4)in the above equation we have 2M =−2

n

X

i<j

γiγj.

This implies

(2.10) 2|M|= 2

n

X

i<j

γ_iγ_j

≤2

n

X

i<j

|γ_i||γ_j|.

(11)

Title Page Contents

JJ II

J I

Close

Now by(2.4),

SLE(G)² =

n

X

i=1

|γ_i|

!2

=

n

X

i=1

|γ_i|²+ 2

n

X

i<j

|γ_i||γ_j|

≥2|M|+ 2

n

X

i<j

|γ_i||γ_j|,

which combined with(2.10)yieldsSLE(G)² ≥4|M|. Thus 2p

|M| ≤SLE(G).

To prove the right-hand inequality, note that for a graph withmedges and no isolated vertex,n ≤2m. By Theorem2.2, we have

SLE(G)≤p

2M₁n ≤p

2M₁(2m) = 2p M₁m.

SinceM₁ ≥m, we obtainSLE(G)≤2M₁.

(12)

Title Page Contents

JJ II

J I

Close

References

[1] C. ADIGA, R. BALAKRISHNAN AND WASIN SO, The skew energy of a graph, (communicated for publication).

[2] C. ADIGAAND M. SMITHA, On the skew Laplacian energy of a digraph, In- ternational Math. Forum, 39 (2009), 1907–1914.

[3] R. GRONE AND R. MERRIS, The Laplacian spectrum of a graph II, SIAM J.

Discrete Math., 7 (1994), 221–229.

[4] R. GRONE, R. MERRIS AND V.S. SUNDER, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl., 11 (1990), 218–238.

[5] I. GUTMAN, The energy of a graph: Old and new results, Algebraic Combina- torics and Applications, Springer-Verlag, Berlin 2001, 196–211.

[6] I. GUTMANANDB. ZHOU, Laplacian energy of a graph. Linear Algebra Appl., 414 (2006), 29–37.

[7] J. KOOLENANDV. MOULTON, Maximal energy graphs, Adv. Appl. Math., 26 (2001), 47–52.

[8] B. ZHOUANDI. GUTMAN, On Laplacian energy of graphs, MATCH Commun.

Math. Comput. Chem., 57 (2007), 211–220.

[9] B. ZHOU, I. GUTMAN AND T. ALEKSIC, A note on Laplacian energy of graphs, MATCH Commun. Math. Comput. Chem., 60 (2008), 441–446.