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.

Keywords:

Weighted Graph, Weighted Signless Laplacian Matrix, Spectral Radius

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=\left(V,E\right)$ be a simple connected weighted graph with vertex set $V=\left\{1,2,\cdots ,n\right\}$ . Let $w_{ij}$ be the positive definite weight matrix of order t of the edge ij and assume that $w_{ij}=w_{ji}$ . The weight of a vertex $i\in V$ defined as $w_i=\sum _{j:j~i}{w}_{ij}$ ; 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\left(G\right)$ of weighted graph G is a block matrix and defined as $Q\left(G\right)={\left(q_{ij}\right)}_{nt\times nt}$ , where

$q_{ij}=\{\begin{array}{l}{w}_i;\text{if}i=j,\\ w_{ij};\text{if}i~j,\\ 0;\text{otherwise}\text{.}\end{array}$

Clearly, $Q\left(G\right)$ is a square matrix of order nt. The eigenvalues may be denoted by $q_1\left(G\right),q_2\left(G\right),\cdots ,q_{nt}\left(G\right)$ , where $q_1\left(G\right)\ge q_2\left(G\right)\ge \cdots \ge q_{nt}\left(G\right)$ . Also let $q_1\left(G\right)$ , $q_1\left(w_i\right)$ and $q_1\left(w_{ij}\right)$ denote the spectral radius of G and the largest eigenvalues of $w_i$ and $w_{ij}$ , respectively. If $A\left(G\right)$ is the weighted adjacency matrix of G, then note that

$Q\left(G\right)=W\left(G\right)+A\left(G\right)$ ,

where $W\left(G\right)=diag\left(w_1,w_2,\cdots ,w_n\right)$ .

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=\frac{1}{d_i}\sum _{j:j~i}{d}_j$ .

$q_1\left(G\right)\le \underset{i\in V}{\max }\left\{2d_i\right\}$ , (1)

$q_1\left(G\right)\le \underset{i\in V}{\max }\left\{d_i+m_i\right\}$ , (2)

$q_1\left(G\right)\le \underset{i\in V}{\max }\left\{\frac{d_i+\sqrt{d_i+8d_i{m}_i}}{2}\right\}$ , (3)

$q_1\left(G\right)\le \underset{i~j}{\max }\left\{d_i+d_j\right\}$ , (4)

$q_1\left(G\right)\le \underset{i~j}{\max }\left\{\frac{d_i+d_j+\sqrt{{\left(d_i-d_j\right)}^2+4m_i{m}_j}}{2}\right\}$ . (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\times n$ matrix with eigenvalues $q_1\ge q_2\ge \cdots \ge q_n$ , then for any $\overline{x}\in {ℝ}^n\left(\overline{x}\ne \overline{0}\right)$ ,

$q_n{\overline{x}}^{\text{T}}\overline{x}\le {\overline{x}}^{\text{T}}A\overline{x}\le q_1{\overline{x}}^{\text{T}}\overline{x}$ .

The equality holds if and only if $\overline{x}$ is an eigenvector of A corresponding to the least eigenvalue $q_n$ .

Lemma 2. [2] .

If A is a real symmetric $n\times n$ matrix with eigenvalues $q_1\ge q_2\ge \cdots \ge q_n$ then for any $\overline{x}\in {ℝ}^n\left(\overline{x}\ne \overline{0}\right)$ , $\overline{y}\in {ℝ}^n\left(\overline{y}\ne \overline{0}\right)$ ,

$\left|{\overline{x}}^{\text{T}}A\overline{y}\right|\le q_1\sqrt{{\overline{x}}^{\text{T}}\overline{x}}\sqrt{{\overline{y}}^{\text{T}}\overline{y}}$ .

The equality holds if and only if $\overline{x}$ is an eigenvector of A corresponding to the largest eigenvalue $q_1$ and $\overline{y}=\alpha \overline{x}$ for some $\alpha \in ℝ$ .

Lemma 3. [3] .

Let G be a weighted graph and let $w_{ij}$ be the positive definite weight matrix of order t of the edge ij. Also let $\overline{x}$ be an eigenvector of $w_{ij}$ corresponding to the largest eigenvalue $q_1\left(w_{ij}\right)$ for all i, j. Then

$q_1\left(w_i\right)=\sum _{j:j~i}{q}_1\left(w_{ij}\right)$ .

Lemma 4. [4] .

Let G be a weighted graph and let $w_{ij}$ be the positive definite weight matrix of order t of the edge ij. If $w_i{w}_{ij}+w_{ij}{w}_j$ and $w_{ij}{w}_{jk}$ are not Hermitian matrices for all j, j∼i and for all k, k∼j, j∼i, then for any $\overline{x}\in {ℂ}^n\left(\overline{x}\ne \overline{0}\right)$ , $\overline{y}\in {ℂ}^n\left(\overline{y}\ne \overline{0}\right)$ ,

$\begin{array}{l}\sum _{j:j~i}\left|{\overline{x}}^{\text{T}}\left(w_i{w}_{ij}+w_{ij}{w}_j\right)\overline{y}\right|\le q_1\left(w_i{w}_{ij}+w_{ij}{w}_j\right)\sqrt{{\overline{x}}^{\text{T}}\overline{x}}\sqrt{{\overline{y}}^{\text{T}}\overline{y}},\\ \sum _{1\le i,k\le n}\sum _{\begin{array}{l}k:k~i\\ k~j\end{array}}\left|{\overline{x}}^{\text{T}}{w}_{ij}{w}_{jk}\overline{y}\right|\le q_1\left(w_{ij}{w}_{jk}\right)\sqrt{{\overline{x}}^{\text{T}}\overline{x}}\sqrt{{\overline{y}}^{\text{T}}\overline{y}}.\end{array}$

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\left(G\right)\le \underset{i\in V}{\max }\left\{2q_1\left(w_i\right)\right\}$ . (6)

Proof.

Let $\overline{x}={\left({\overline{x_1}}^{\text{T}},{\overline{x_2}}^{\text{T}},\cdots ,{\overline{x_n}}^{\text{T}}\right)}^{\text{T}}$ be an eigenvector corresponding to the eigenvalue

$q_1\left(G\right)$ and $\overline{x_i}$ be the vector component of $\overline{x}$ such that

${\overline{x_i}}^{\text{T}}\overline{x_i}=\underset{j\in V}{\max }\left\{{\overline{x_j}}^{\text{T}}\overline{x_j}\right\}$ . (7)

Since $\overline{x}$ is nonzero, so is $\overline{x_i}$ . We have

$q_1\left(G\right)\overline{x}=Q\left(G\right)\overline{x}=W\left(G\right)\overline{x}+A\left(G\right)\overline{x}$ . (8)

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

$q_1\left(G\right)\overline{x_i}=w_i\overline{x_i}+\sum _{j:j~i}{w}_{ij}\overline{x_j}$ ,

i.e.,

${\overline{x_i}}^{\text{T}}\left(q_1\left(G\right){{\rm I}}_{t\times t}-w_i\right)\overline{x_i}=\sum _{j:j~i}{\overline{x_i}}^{\text{T}}{w}_{ij}{x}_j\overline{\le }\sum _{j:j~i}\left|{\overline{x_i}}^{\text{T}}{w}_{ij}\overline{x_j}\right|$ .

From (7) and using Lemma 2, we get

$\le {\overline{x_i}}^{\text{T}}\overline{x_i}\sum _{j:j~i}{q}_1\left(w_{ij}\right)$ .

From Lemma 1 and Lemma 3, we have

$\left(q_1\left(G\right)-q_1\left(w_i\right)\right){\overline{x_i}}^{\text{T}}\overline{x_i}\le {\overline{x_i}}^{\text{T}}\left(q_1\left(G\right){{\rm I}}_{t\times t}-w_i\right)\overline{x_i}\le {\overline{x_i}}^{\text{T}}\overline{x_i}{q}_1\left(w_i\right)$ .

Thus

$q_1\left(G\right)\le \underset{i\in V}{\max }\left\{2q_1\left(w_i\right)\right\}$ .

Hence the theorem follows.

Corollary 6.

Let G be a simple connected weighted graph where each edge weight $w_{ij}$ is a positive number. Then

$q_1\left(G\right)\le \underset{i\in V}{\max }\left\{2w_i\right\}$ .

Proof.

For weighted graphs where the edge weights $w_{ij}$ are positive number, we have $q_1\left(w_{ij}\right)=w_{ij}$ and $q_1\left(w_i\right)=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\left(G\right)\le \underset{i\in V}{\max }\left\{2d_i\right\}$ ,

where $d_i$ is the degree of vertex i.

Proof.

For an unweighted graph, $w_{ij}=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\left(G\right)\le \underset{i~j}{\max }\left\{q_1\left(w_i\right)+\sum _{k:k~j}{q}_1\left(w_{jk}\right)\right\}$ . (9)

Proof.

Let us consider the matrix $M\left(G\right)=diag\left(q_1\left(w_1\right)I_{t\times t},q_1\left(w_2\right)I_{t\times t},\cdots ,q_1\left(w_n\right)I_{t\times t}\right)$ . The $\left(i,j\right)$ -th element of $M{\left(G\right)}^{-1}Q\left(G\right)M\left(G\right)$ is

$\{\begin{array}{l}{w}_i;\text{if}i=j,\\ \frac{q_1\left(w_j\right)}{q_1\left(w_i\right)}{w}_{ij};\text{if}i~j,\\ 0;\text{otherwise}\text{.}\end{array}$

Let $\overline{x}={\left({\overline{x_1}}^{\text{T}},{\overline{x_2}}^{\text{T}},\cdots ,{\overline{x_n}}^{\text{T}}\right)}^{\text{T}}$ be an eigenvector corresponding to the eigenvalue $q_1\left(G\right)$ of $M{\left(G\right)}^{-1}Q\left(G\right)M\left(G\right)$ and $\overline{x_i}$ be the vector component of $\overline{x}$ such that

${\overline{x_i}}^{\text{T}}\overline{x_i}=\underset{j\in V}{\max }\left\{{\overline{x_j}}^{\text{T}}{x}_j\right\}\overline{}$ . (10)

Since $\overline{x}$ is nonzero, so is $\overline{x_i}$ . We have

$\left\{M{\left(G\right)}^{-1}Q\left(G\right)M\left(G\right)\right\}\overline{x}=q_1\left(G\right)\overline{x}$ . (11)

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

$q_1\left(G\right)\overline{x_i}=w_i\overline{x_i}+\sum _{j:j~i}\frac{q_1\left(w_j\right)}{q_1\left(w_i\right)}{w}_{ij}\overline{x_j}$ ,

i.e.,

${\overline{x_i}}^{\text{T}}\left(q_1\left(G\right){{\rm I}}_{t\times t}-w_i\right)\overline{x_i}\le \sum _{j:j~i}\frac{q_1\left(w_j\right)}{q_1\left(w_i\right)}\left|{\overline{x_i}}^{\text{T}}{w}_{ij}\overline{x_j}\right|$ .

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

$\begin{array}{l}\left(q_1\left(G\right)-q_1\left(w_i\right)\right){\overline{x_i}}^{\text{T}}\overline{x_i}\\ \le {\overline{x_i}}^{\text{T}}\left(q_1\left(G\right){{\rm I}}_{t\times t}-w_i\right)\overline{x_i}\le {\overline{x_i}}^{\text{T}}\overline{x_i}\sum _{j:j~i}\frac{q_1\left(w_j\right)}{q_1\left(w_i\right)}{q}_1\left(w_{ij}\right)\\ \le {\overline{x_i}}^{\text{T}}\overline{x_i}\frac{1}{q_1\left(w_i\right)}\underset{j:j~i}{\max }\left\{q_1\left(w_j\right)\right\}\sum _{j:j~i}{q}_1\left(w_{ij}\right).\end{array}$ (12)

Thus

$q_1\left(G\right)\le \underset{i~j}{\max }\left\{q_1\left(w_i\right)+\sum _{k:k~j}{q}_1\left(w_{jk}\right)\right\}$ .

Hence the theorem follows.

Corollary 9.

Let G be a simple connected weighted graph where each edge weight $w_{ij}$ is a positive number. Then

$q_1\left(G\right)\le \underset{i~j}{\max }\left\{w_i+w_j\right\}$ .

Proof.

For weighted graphs where the edge weights $w_{ij}$ are positive number, we have $q_1\left(w_{ij}\right)=w_{ij}$ and $q_1\left(w_i\right)=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\left(G\right)\le \underset{i~j}{\max }\left\{d_i+d_j\right\}$ ,

where $d_i$ is the degree of vertex i.

Proof.

For an unweighted graph, $w_{ij}=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\left(G\right)\le \underset{i~j}{\max }\left\{q_1\left(w_i\right)+{\gamma }_i\right\}$ , (13)

where ${\gamma }_i=\frac{\sum _{j:j~i}{q}_1\left(w_{ij}\right)q_1\left(w_j\right)}{q_1\left(w_i\right)}.$

Proof.

From (12), we get

$\begin{array}{c}{q}_1\left(G\right)\le q_1\left(w_i\right)+\sum _{j:j~i}\frac{q_1\left(w_j\right)}{q_1\left(w_i\right)}{q}_1\left(w_{ij}\right)\\ \le \underset{i\in V}{\max }\left\{q_1\left(w_i\right)+{\gamma }_i\right\}.\end{array}$

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.

Cite this paper

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

References