Share This Article:

A Note on the Spectral Radius of Weighted Signless Laplacian Matrix

Abstract Full-Text HTML XML Download Download as PDF (Size:327KB) PP. 53-63
DOI: 10.4236/alamt.2018.81006    415 Downloads   813 Views   Citations

ABSTRACT

A weighted graph is a graph that has a numeric label associated with each edge, called the weight of edge. In many applications, the edge weights are usually represented by nonnegative integers or square matrices. The weighted signless Laplacian matrix of a weighted graph is defined as the sum of adjacency matrix and degree matrix of same weighted graph. In this paper, a brief overview of the notation and concepts of weighted graphs that will be used throughout this study is given. In Section 2, the weighted signless Laplacian matrix of simple connected weighted graphs is considered, some upper bounds for the spectral radius of the weighted signless Laplacian matrix are obtained and some results on weighted and unweighted graphs are found.

1. Introduction

A weighted graph is a graph that has a numeric label associated with each edge, called the weight of edge. In many applications, the edge weights are usually represented by nonnegative integers or square matrices. In this paper, we generally deal with simple connected weighted graphs where the edge weights are positive definite square matrices. Let G = ( V , E ) be a simple connected weighted graph with vertex set V = { 1 , 2 , , n } . Let w i j be the positive definite weight matrix of order t of the edge ij and assume that w i j = w j i . The weight of a vertex i V defined as w i = j : j ~ i w i j ; where i ~ j denotes the vertex j is adjacent to i.

Unless otherwise specified, by a weighted graph we mean a graph with each edge weight is a positive definite square matrix.

The weighted signless Laplacian matrix Q ( G ) of weighted graph G is a block matrix and defined as Q ( G ) = ( q i j ) n t × n t , where

q i j = { w i ; if i = j , w i j ; if i ~ j , 0 ; otherwise .

Clearly, Q ( G ) is a square matrix of order nt. The eigenvalues may be denoted by q 1 ( G ) , q 2 ( G ) , , q n t ( G ) , where q 1 ( G ) q 2 ( G ) q n t ( G ) . Also let q 1 ( G ) , q 1 ( w i ) and q 1 ( w i j ) denote the spectral radius of G and the largest eigenvalues of w i and w i j , respectively. If A ( G ) is the weighted adjacency matrix of G, then note that

Q ( G ) = W ( G ) + A ( G ) ,

where W ( G ) = d i a g ( w 1 , w 2 , , w n ) .

In literature, there are a lot of studies deal with upper and lower bounds for the spectral radius of signless Laplacian matrix of unweighted graphs. For a simple connected and unweighted graph G, there are some known upper bounds on the spectral radius of signless Laplacian matrix as follows such that d i is

degree of vertex i and m i = 1 d i j : j ~ i d j .

q 1 ( G ) max i V { 2 d i } , (1)

q 1 ( G ) max i V { d i + m i } , (2)

q 1 ( G ) max i V { d i + d i + 8 d i m i 2 } , (3)

q 1 ( G ) max i ~ j { d i + d j } , (4)

q 1 ( G ) max i ~ j { d i + d j + ( d i d j ) 2 + 4 m i m j 2 } . (5)

In this paper, some upper bounds for the spectral radius of signless Laplacian matrix of weighted graphs are given. Also some results on weighted and unweighted graphs are obtained by using these bounds. The following lemmas are convenient for the graphs we consider.

Lemma 1. [1] .

If A is a real symmetric n × n matrix with eigenvalues q 1 q 2 q n , then for any x ¯ n ( x ¯ 0 ¯ ) ,

q n x ¯ T x ¯ x ¯ T A x ¯ q 1 x ¯ T x ¯ .

The equality holds if and only if x ¯ is an eigenvector of A corresponding to the least eigenvalue q n .

Lemma 2. [2] .

If A is a real symmetric n × n matrix with eigenvalues q 1 q 2 q n then for any x ¯ n ( x ¯ 0 ¯ ) , y ¯ n ( y ¯ 0 ¯ ) ,

| x ¯ T A y ¯ | q 1 x ¯ T x ¯ y ¯ T y ¯ .

The equality holds if and only if x ¯ is an eigenvector of A corresponding to the largest eigenvalue q 1 and y ¯ = α x ¯ for some α .

Lemma 3. [3] .

Let G be a weighted graph and let w i j be the positive definite weight matrix of order t of the edge ij. Also let x ¯ be an eigenvector of w i j corresponding to the largest eigenvalue q 1 ( w i j ) for all i, j. Then

q 1 ( w i ) = j : j ~ i q 1 ( w i j ) .

Lemma 4. [4] .

Let G be a weighted graph and let w i j be the positive definite weight matrix of order t of the edge ij. If w i w i j + w i j w j and w i j w j k are not Hermitian matrices for all j, j∼i and for all k, k∼j, j∼i, then for any x ¯ n ( x ¯ 0 ¯ ) , y ¯ n ( y ¯ 0 ¯ ) ,

j : j ~ i | x ¯ T ( w i w i j + w i j w j ) y ¯ | q 1 ( w i w i j + w i j w j ) x ¯ T x ¯ y ¯ T y ¯ , 1 i , k n k : k ~ i k ~ j | x ¯ T w i j w j k y ¯ | q 1 ( w i j w j k ) x ¯ T x ¯ y ¯ T y ¯ .

2. Main Results

In this section, some upper bounds for the spectral radius of weighted signless Laplacian matrix are found.

Theorem 5.

Let G be a simple connected weighted graph. Then

q 1 ( G ) max i V { 2 q 1 ( w i ) } . (6)

Proof.

Let x ¯ = ( x 1 ¯ T , x 2 ¯ T , , x n ¯ T ) T be an eigenvector corresponding to the eigenvalue

q 1 ( G ) and x i ¯ be the vector component of x ¯ such that

x i ¯ T x i ¯ = max j V { x j ¯ T x j ¯ } . (7)

Since x ¯ is nonzero, so is x i ¯ . We have

q 1 ( G ) x ¯ = Q ( G ) x ¯ = W ( G ) x ¯ + A ( G ) x ¯ . (8)

From the i-th Equation of (8), we get

q 1 ( G ) x i ¯ = w i x i ¯ + j : j ~ i w i j x j ¯ ,

i.e.,

x i ¯ T ( q 1 ( G ) Ι t × t w i ) x i ¯ = j : j ~ i x i ¯ T w i j x j ¯ j : j ~ i | x i ¯ T w i j x j ¯ | .

From (7) and using Lemma 2, we get

x i ¯ T x i ¯ j : j ~ i q 1 ( w i j ) .

From Lemma 1 and Lemma 3, we have

( q 1 ( G ) q 1 ( w i ) ) x i ¯ T x i ¯ x i ¯ T ( q 1 ( G ) Ι t × t w i ) x i ¯ x i ¯ T x i ¯ q 1 ( w i ) .

Thus

q 1 ( G ) max i V { 2 q 1 ( w i ) } .

Hence the theorem follows.

Corollary 6.

Let G be a simple connected weighted graph where each edge weight w i j is a positive number. Then

q 1 ( G ) max i V { 2 w i } .

Proof.

For weighted graphs where the edge weights w i j are positive number, we have q 1 ( w i j ) = w i j and q 1 ( w i ) = w i , for all i , j . Using Theorem 5 we get the required result.

Corollary 7. [5] .

Let G be a simple connected unweighted graph. Then

q 1 ( G ) max i V { 2 d i } ,

where d i is the degree of vertex i.

Proof.

For an unweighted graph, w i j = 1 and w i = d i for all i , j and i ~ j . Using Corollary 6 we get the required result.

Theorem 8.

Let G be a simple connected weighted graph. Then

q 1 ( G ) max i ~ j { q 1 ( w i ) + k : k ~ j q 1 ( w j k ) } . (9)

Proof.

Let us consider the matrix M ( G ) = d i a g ( q 1 ( w 1 ) I t × t , q 1 ( w 2 ) I t × t , , q 1 ( w n ) I t × t ) . The ( i , j ) -th element of M ( G ) 1 Q ( G ) M ( G ) is

{ w i ; if i = j , q 1 ( w j ) q 1 ( w i ) w i j ; if i ~ j , 0 ; otherwise .

Let x ¯ = ( x 1 ¯ T , x 2 ¯ T , , x n ¯ T ) T be an eigenvector corresponding to the eigenvalue q 1 ( G ) of M ( G ) 1 Q ( G ) M ( G ) and x i ¯ be the vector component of x ¯ such that

x i ¯ T x i ¯ = max j V { x j ¯ T x j } ¯ . (10)

Since x ¯ is nonzero, so is x i ¯ . We have

{ M ( G ) 1 Q ( G ) M ( G ) } x ¯ = q 1 ( G ) x ¯ . (11)

From the i-th Equation of (11), we get

q 1 ( G ) x i ¯ = w i x i ¯ + j : j ~ i q 1 ( w j ) q 1 ( w i ) w i j x j ¯ ,

i.e.,

x i ¯ T ( q 1 ( G ) Ι t × t w i ) x i ¯ j : j ~ i q 1 ( w j ) q 1 ( w i ) | x i ¯ T w i j x j ¯ | .

From (10) and using Lemma 1 and Lemma 2, we get

( q 1 ( G ) q 1 ( w i ) ) x i ¯ T x i ¯ x i ¯ T ( q 1 ( G ) Ι t × t w i ) x i ¯ x i ¯ T x i ¯ j : j ~ i q 1 ( w j ) q 1 ( w i ) q 1 ( w i j ) x i ¯ T x i ¯ 1 q 1 ( w i ) max j : j ~ i { q 1 ( w j ) } j : j ~ i q 1 ( w i j ) . (12)

Thus

q 1 ( G ) max i ~ j { q 1 ( w i ) + k : k ~ j q 1 ( w j k ) } .

Hence the theorem follows.

Corollary 9.

Let G be a simple connected weighted graph where each edge weight w i j is a positive number. Then

q 1 ( G ) max i ~ j { w i + w j } .

Proof.

For weighted graphs where the edge weights w i j are positive number, we have q 1 ( w i j ) = w i j and q 1 ( w i ) = w i , for all i , j . Using Theorem 8 we get the required result.

Corollary 10. [6] .

Let G be a simple connected unweighted graph. Then

q 1 ( G ) max i ~ j { d i + d j } ,

where d i is the degree of vertex i.

Proof.

For an unweighted graph, w i j = 1 and w i = d i for all i , j and i ~ j . Using Corollary 9 we get the required result.

Theorem 11.

Let G be a simple connected weighted graph. Then,

q 1 ( G ) max i ~ j { q 1 ( w i ) + γ i } , (13)

where γ i = j : j ~ i q 1 ( w i j ) q 1 ( w j ) q 1 ( w i ) .

Proof.

From (12), we get

q 1 ( G ) q 1 ( w i ) + j : j ~ i q 1 ( w j ) q 1 ( w i ) q 1 ( w i j ) max i V { q 1 ( w i ) + γ i } .

The proof is complete.

Corollary 12.

Let G be a simple connected weighted graph where each edge weight is a positive number. Then

,

where.

Proof.

For weighted graphs where the edge weights are positive number, we have and, for all. Using Theorem 11 we get the required result.

Corollary 13. [6] .

Let G be a simple connected unweighted graph. Then

,

where is the degree of vertex i and is the average of the degrees of the vertices adjacent to vertex i.

Proof.

For an unweighted graph, and for all and. Using Corollary 12 we get the required result.

Theorem 14.

Let G be a simple connected weighted graph. Then

, (14)

where

Proof.

Let be an eigenvector corresponding to the eigenvalue. We assume that be the vector component of such that

. (15)

Since is nonzero, so is. We have

In order to prove the Inequality (14), we consider a simple quadratic function of:

(16)

From the i-th Equation of (16), we get

i.e.,

Since is the positive definite matrix of edge ij, matrix is also positive definite. From Lemma 1, we have

(17)

Four cases arise;

1) and are real symmetric matrices for all j, j∼i and for all k, k∼j, j∼i.

2) is a real symmetric matrix for all j, j∼i and is not a real symmetric matrix for all k, k∼j, j∼i.

3) is not a real symmetric matrix for all j, j∼i and is a real symmetric matrix for all k, k∼j, j∼i.

4) and are not real symmetric matrices for all j, j∼i and for all k, k∼j, j∼i.

From (15), (17) and using Lemma 2 and Lemma 4, we get

(18)

for Case (1), Case (2), Case (3) and Case (4). Hence,

From Lemma 3, we have

i.e.,

Thus

From the inequality above, for every different value to b, we can get several distinct upper bounds. In particular, if, we get

.

This completes the proof.

Corollary 15.

Let G be a simple connected weighted graph where each edge weight is a positive number. Then

,

where.

Proof.

For weighted graphs where the edge weights are positive number, we have and, for all. Using Theorem 14 we get the required result.

Corollary 16. [5] .

Let G be a simple connected unweighted graph. Then

,

where is the degree of vertex i and is the average of the degrees of the vertices adjacent to vertex i.

Proof.

For an unweighted graph, and for all and. Using Corollary 15 we get the required result.

Theorem 17.

Let G be a simple connected weighted graph. Then,

, (19)

where

Proof.

. The -th element of is

Let be an eigenvector corresponding to the eigenvalue of, and are the vector components of such that

, (20)

. (21)

Since is nonzero, so is. We have

. (22)

From the i-th Equation of (22), we get

.

From Lemma 2, we get

. (23)

From (21), (23) and using Lemma 1, we get

(24)

Similarly, from the j-th Equation of (22), we have

(25)

From (24) and (25), we get

Thus

.

Hence the theorem is proved.

Corollary 18.

Let G be a simple connected weighted graph where each edge weight is a positive number. Then

,

where.

Proof.

For weighted graphs where the edge weights are positive number, we have and, for all. Using Theorem 17 we get the required result.

Corollary 19. [7] .

Let G be a simple connected unweighted graph. Then

,

where is the degree of vertex i and is the average of the degrees of the vertices adjacent to vertex i.

Proof.

For an unweighted graph, and for all and. Using Corollary 18 we get the required result.

Conflict of Interests

The authors declare that there is no conlict of interests regarding the publication of this paper.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Büyükköse, Ş. , Mutlu, N. and Gök, G. (2018) A Note on the Spectral Radius of Weighted Signless Laplacian Matrix. Advances in Linear Algebra & Matrix Theory, 8, 53-63. doi: 10.4236/alamt.2018.81006.

References

[1] Zhang, F. (1999) Matrix Theory: Basic Results and Techniques. Springer-Verlag, New York.
https://doi.org/10.1007/978-1-4757-5797-2
[2] Horn, R.A. and Johnson, C.R. (1985) Matrix Analysis. Cambridge University Press, New York.
https://doi.org/10.1017/CBO9780511810817
[3] Das, K.C. (2007) Extremal Graph Characterization from the Upper Bound of the Laplacian Spectral Radius of Weighted Graphs. Linear Algebra and Its Applications, 427, 55-69.
https://doi.org/10.1016/j.laa.2007.06.018
[4] Büyükköse, Ş. and Mutlu, N. (2015) The Upper Bound for the Largest Signless Laplacian Eigenvalue of Weighted Graphs. Gazi University Journal of Science, 28, 709-714.
[5] Oliveira, C.S., Lima, L.S., Abreu, N.M. and Hansen, P. (2010) Bounds on the Index of the Signless Laplacian of a Graph. Discrete Applied Mathematics, 158, 355-360.
https://doi.org/10.1016/j.dam.2009.06.023
[6] Anderson, W.N. and Morley, T.D. (1985) Eigenvalues of the Laplacian of a Graph. Linear and Multilinear Algebra, 18, 141-145.
https://doi.org/10.1080/03081088508817681
[7] Das, K.C. (2004) A Characterization on Graphs Which Achieve the Upper Bound for the Largest Laplacian Eigenvalue of Graphs. Linear Algebra and Its Applications, 376, 173-186.
https://doi.org/10.1016/j.laa.2003.06.009

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.