Contents

The bounds for topological invariants of a weighted graph using traces

Author(s): Emre Sevgi1, Gül Özkan Kizilirmak, Serife Büyükköse
1Department of Mathematics, Faculty of Science, Gazi University, Ankara, Turkey.
Copyright © Emre Sevgi, Gül Özkan Kizilirmak, Serife Büyükköse. 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.

Abstract

In this paper, we obtain the bounds for the Laplacian eigenvalues of a weighted graph using traces. Then, we find the bounds for the Kirchhoff and Laplacian Estrada indices of a weighted graph. Finally, we define the Laplacian energy of a weighted graph and get the upper bound for this energy.

Keywords: Laplacian energy; Kirchhoff index; Laplacian Estrada index; Weighted graph.

1. Introduction

Let \(G\) be a weighted graph with \(n\) vertices and \(m\) edges. The Laplacian matrix \(L\) of a weighted graph \(G\) is the \(n\times n\) matrix defined as follows:

\[l_{ij}=\left\{ \begin{array}{cc} w_{i}, & \text{if }i=j \\ -w_{ij}, & \text{if }i\sim j \\ 0, & \text{otherwise.} \end{array} \right.\] Here, the weight \(w_{i}=\underset{i\sim j}{\overset{}{\sum }}w_{ij}\) is the sum of the weights of edges incident on vertex \(i.\) There are some studies on indices of graphs using Laplacian eigenvalues. For any connected graph \(G\) with \(n\) vertices, the Kirchhoff index is \[Kf(G)=n\sum_{k=1}^{n-1}{\frac{1}{\lambda _{k}}},\] where \(\lambda _{k}\) are the Laplacian eigenvalues of \(G\) [1].

Let \(G\) be a graph with \(n\) vertices without loops and multiple edges. Then, the Laplacian Estrada index of \(G\) is \[LEE(G)=\sum_{i=1}^{n}e^{\lambda _{i}},\] where \(\lambda _{i}\) are the Laplacian eigenvalues of \(G\) [2] .

The energy \(E(G)\) of a graph \(G\) defined as the sum of the absolute values of its eigenvalues. In 2006, Gutman and Zhou defined the Laplacian energy of a graph as \[LE(G)=\sum_{i=1}^{n}\left\vert \mu _{i}-\frac{2m}{n}\right\vert,\] where \(n\geq \mu _{1}\geq \mu _{2}\geq \cdot \cdot \cdot \geq \mu _{n}=0\) [3].

In the following theorems, the bounds for the eigenvalues of a matrix is given by using the trace of the matrix [4].

Theorem 1. Let \(A\) be an \(n\times n\) complex matrix. \(A^{\ast }\) denotes the conjugate transpose of \(A.\) Let \(B=AA^{\ast }\) with eigenvalues \(\lambda _{n}(B)\leq \cdots \leq \lambda _{1}(B).\) Then,

\[m-s\sqrt{n-1}\leq \lambda _{n}(B)\leq m-\frac{s}{\sqrt{n-1}}\] and

\[m+\frac{s}{\sqrt{n-1}}\leq \lambda _{1}(B)\leq m+s\sqrt{n-1},\] where \(m=\dfrac{trB}{n}\) and \(s^{2}=\dfrac{trB^{2}}{n}-m^{2}.\)

Theorem 2. Let \(A,\) \(m\) and \(s^{2}\) be defined as in Theorem 1, then

\[m-s\sqrt{\frac{k-1}{n-k+1}}\leq \lambda _{k}(B)\leq m+s\sqrt{\frac{n-1}{k}}. \label{inqk}\tag{1}\]

By using the above theorems, the bounds for the Laplacian eigenvalues for a connected simple graph were established [5].

In the next chapter, we will obtain the bounds for the Laplacian eigenvalues of a weighted graph. Then, we will find the bounds for the Kirchhoff and Laplacian Estrada indices of a weighted graph. Finally, we will define the Laplacian energy of a weighted graph and get the upper bound for this energy.

2. Discussion and Main Results

Theorem 3. Let \(G\) be a weighted graph with \(n\) vertices and \(L\) be the Laplacian matrix of \(G\) with the eigenvalues \(\lambda _{n}(L)\leq \cdots \leq \lambda _{1}(L)\). Then,

\[m-s\sqrt{n-1}\leq \lambda _{n}(L)\leq m-\frac{s}{\sqrt{n-1}}\] and

\[m+\frac{s}{\sqrt{n-1}}\leq \lambda _{1}(L)\leq m+s\sqrt{n-1},\] where

\[m=\dfrac{1}{n}\underset{i=1}{\overset{n}{\sum }}w_{i}\] and

\[s^{2}=\frac{n-1}{n^{2}}\underset{i=1}{\overset{n}{\sum }}w_{i}^{2}+\dfrac{2}{ n}\underset{i\sim j}{\overset{}{\sum }}w_{ij}^{2}-\dfrac{2}{n^{2}}\underset{ i<j}{\overset{n}{\sum }}w_{i}w_{j}.\]

Proof. By Theorem 1, we can write \(m=\dfrac{trL}{n}.\) So, by the definition of weighted Laplacian matrix, we have

\[m=\dfrac{trL}{n}=\dfrac{1}{n}\underset{i=1}{\overset{n}{\sum }}w_{i}.\]

Moreover, evaluating the matrix \(L^{2}\), when \(i=j\) we find the \((i,j)\_th\) elements as

\[L_{ij}=w_{i}^{2}+\underset{i\sim j}{\overset{}{\sum }}w_{ij}^{2}. \label{element}\tag{2}\]

Again, by Theorem 1, we can write \(s^{2}=\dfrac{trL^{2}}{n}-m^{2}.\) So, by using (2), we have

\[\begin{array}{ll} s^{2} & =\dfrac{1}{n}\left( \underset{i=1}{\overset{n}{\sum }}w_{i}^{2}+2 \underset{i\sim j}{\overset{}{\sum }}w_{ij}^{2}\right) -\dfrac{1}{n^{2}} \left( \underset{i=1}{\overset{n}{\sum }}w_{i}\right) ^{2} =\dfrac{n-1}{n^{2}}\underset{i=1}{\overset{n}{\sum }}w_{i}^{2}+\dfrac{2}{n} \underset{i\sim j}{\overset{}{\sum }}w_{ij}^{2}-\dfrac{2}{n^{2}}\underset{i<j }{\overset{n}{\sum }}w_{i}w_{j}. \end{array}\] ◻

Example 1. Let we have the weighted graph \(G\) shown in the following figure.

weighted Laplacian matrix of \(G\) is \[L= \begin{bmatrix} 5 & -5 & 0 & 0 \\ -5 & 13 & -2 & -6 \\ 0 & -2 & 6 & -4 \\ 0 & -6 & -4 & 10 \end{bmatrix}\] and the eigenvalues are \(\lambda _{1}=18.89,\) \(\lambda _{2}=10.79,\) \(\lambda _{3}=4.31\) and \(\lambda _{4}=0.\)

By using Theorem 3, we get \(m=8.5,\) \(s^{2}=50.75\) and so \( s=7.12.\)Also, by the inequality (2) we get some bounds for the eigenvalues \(\lambda _{2}\ \)and \(\lambda _{3}\) as

\[4.38\leq \lambda _{2}=10.79\leq 15.62,\] \[1.38\leq \lambda _{3}=4.31\leq 12.61.\]

By Theorem 3, we get a bound for the largest eigenvalue \(\lambda _{1}\) as \[12.61\leq \lambda _{1}=18.89\leq 20.83.\]

Now, we will give an upper and lower bound for the Kirchhoff index of a weighted graph using the trace of the weighted Laplacian matrix.

Theorem 4. Let \(G\) be a weighted graph with \(n\) vertices, then

\[\frac{n(n-1)}{m+s\sqrt{n-1}}\leq Kf(G)\leq \frac{n(n-1)}{m-s\sqrt{\frac{n-2}{ 2}}}, \label{kirchhoff}\tag{3}\]

where \(m\) and \(s^{2}\) are defined in Theorem 3.

Proof. We know that the largest eigenvalue of Laplacian matrix of \(G\) has the following bound

\[m+\frac{s}{\sqrt{n-1}}\leq \lambda _{1}(L)\leq m+s\sqrt{n-1}.\]

Assume that all eigenvalues of \(L\) are equal to the largest eigenvalue \( \lambda _{1}(L),\) then,

\[\begin{array}{ll} Kf(G) & \geq n(n-1)\dfrac{1}{\lambda _{1}(L)} \\ & \geq \dfrac{n(n-1)}{m+s\sqrt{n-1}}. \end{array}\]

Conversely, let all eigenvalues of \(L\) be equal to the smallest eigenvalue \( \lambda _{n-1}(L)\) different from zero, then by the inequality (1) we can write

\[m-s\sqrt{\frac{n-2}{2}}\leq \lambda _{n-1}(L)\leq m+s\sqrt{\frac{1}{n-1}}, \label{boundn-1}\tag{4}\] and so,

\[\begin{array}{ll} Kf(G) & \leq n(n-1)\dfrac{1}{\lambda _{n-1}(L)} \leq \dfrac{n(n-1)}{m-s\sqrt{\frac{n-2}{2}}}. \end{array}\] ◻

Example 2. Let we have the graph defined in Example 1 with \(m=8.5\) and \( s=7.12.\)

The Kirchhoff index of \(G\) is evaluated as

\[Kf(G)=4\left( \frac{1}{18.89}+\frac{1}{10.79}+\frac{1}{4.31}\right) =1.50\]

By using the inequality (3) we get the following bound for Kirchhoff index of \(G\)

\[0.57\leq Kf(G)=1.50\leq 8.69.\]

Now, we will give an upper and lower bound for the Laplacian Estrada index of a weighted graph using the trace of the weighted Laplacian matrix.

Theorem 5. Let \(G\) be a weighted graph with \(n\) vertices, then

\[1+(n-1)e^{m-s\sqrt{\frac{n-2}{2}}}\leq LEE(G)\leq 1+(n-1)e^{m+s\sqrt{n-1}}, \label{estrada}\]

where \(m\) and \(s^{2}\) are defined in Theorem 3.

Proof. We know that the largest eigenvalue of Laplacian matrix of \(G\) has the following bound

\[m+\frac{s}{\sqrt{n-1}}\leq \lambda _{1}(L)\leq m+s\sqrt{n-1}.\]

Assume that all eigenvalues of \(L\) are equal to the largest eigenvalue \( \lambda _{1}(L),\) then,

\[\begin{array}{ll} LEE(G) & \leq 1+(n-1)e^{\lambda _{1}(L)} \\ & \leq 1+(n-1)e^{m+s\sqrt{n-1}}. \end{array}\]

Conversely, let all eigenvalues of \(L\) be equal to the smallest eigenvalue \( \lambda _{n-1}(L)\) different from zero, then by using the bounds (4) for \(\lambda _{n-1}(L),\) we get \[\begin{array}{ll} LEE(G) & \geq 1+(n-1)e^{\lambda _{n-1}(L)} \\ & \geq 1+(n-1)e^{m-s\sqrt{\frac{n-2}{2}}}. \end{array}\] ◻

Example 3. Let we have the graph defined in Example 1with \(m=8.5\) and \( s=7.12.\)

The Laplacian Estrada index of \(G\) is evaluated as

\[LEE(G)=1+e^{18.89}+e^{10.79}+e^{4.31}=1599391195.21\]

By using the inequality (5) we get the following bound for Laplacian Estrada index of \(G\)

\[33.41\leq LEE(G)=1599391195.21\leq 3296780717.01.\]

Definition 6. Laplacian energy of a weighted graph \(G\) is defined as

\[LE^{w}(G)=\overset{n-1}{\underset{i=1}{\sum }}\left\vert \mu _{i}-\frac{ \sum\limits_{i=1}^{n}w_{i}}{n}\right\vert ,\] where \(\mu _{i}\) \((i=1,…n)\) are Laplacian eigenvalues and \(w_{i}\) \( (i=1,…n)\) are the weights of the edges of the weighted graph \(G.\)

Theorem 7. The upper bound for the Laplacian energy of a weighted graph \(G\) is

\[LE^{w}(G)\leq \left( n-1\right) \left[ m+s\sqrt{n-1}-w_{\min }\right] ,\] where \(m=\dfrac{trL(G)}{n}\) and \(s^{2}=\dfrac{trL(G)^{2}}{n}-m^{2}.\)

Proof. By the above definition, Laplacian energy of a weighted graph \(G\) is

\[LE^{w}(G)=\overset{n-1}{\underset{i=1}{\sum }}\left\vert \mu _{i}-\frac{ \sum\limits_{i=1}^{n}w_{i}}{n}\right\vert .\] If we take the maximum Laplacian eigenvalue \(\mu _{1}\) and the minimum edge weight \(w_{\min }\) instead of all eigenvalues and all edges, respectively, we get an upper bound for Laplacian energy. Then,

\[\begin{array}{ll} LE^{w}(G) & \leq \overset{n-1}{\underset{i=1}{\sum }}\left\vert \mu _{1}-w_{\min }\right\vert \leq (n-1)\left[ \mu _{1}-w_{\min }\right] \leq \left( n-1\right) \left[ m+s\sqrt{n-1}-w_{\min }\right] . \end{array}\] ◻

Example 4. Let we have the graph defined in Example 1 with \(m=8.5\) and \( s=7.12.\)

The Laplacian energy of \(G\) is evaluated as

\[LE^{w}(G)=16.865.\]

Using the above theorem, we get the upper bound for the Laplacian energy of \( G\) as

\[LE^{w}(G)\leq 47.493.\]

References

  1. Gutman, I. & Mohar, B. (1996). The Quasi-Wiener and the Kirchhoff indices coincide. Journal of Chemical Information and Computer Sciences, 36(5), 982–985.

  2. Fath-Tabar, G. H., Ashrafi, A. R., & Gutman, I. (2009). Note on Estrada and L-Estrada indices of graphs. Bulletin (Académie serbe des sciences et des arts. Classe des sciences mathématiques et naturelles. Sciences mathématiques), 1-16.

  3. Gutman, I. & Zhou, B. (2006). Laplacian energy of a graph. Linear Algebra and its Applications , 414, 29–37.

  4. Wolkowicz, H. & Styan, G. (1980). Bounds for eigenvalues using traces. Linear Algebra and its Applications , 29, 471–506.

  5. Maden, A. D. & Buyukkose, S. (2012). Bounds for Laplacian graph eigenvalues. Mathematical Inequalities & Applications, 12, 529–536.