# On the Spectrum of Laplacian Matrix

Authors: Akbar Jahanbani; Seyed Mahmoud Sheikholeslami; Rana Khoeilar
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

LetG be a simple graph of order n. The matrix ℒG=DG−AG is called the Laplacian matrix of G, where DG and AG denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let l1G, ln−1G be the largest eigenvalue, the second smallest eigenvalue of ℒG respectively, and λ1G be the largest eigenvalue of AG. In this paper, we will present sharp upper and lower bounds for l1G and ln−1G. Moreover, we investigate the relation between l1G and λ1G.


---

## Body

## 1. Introduction

We begin with the preliminaries which are required throughout this paper. LetG be a simple graph with vertex set V=VG and edge set EG. The integers n=nG=VG and ε=εG=EG are the order and the size of the graph G, respectively. The open neighborhood of vertex vi is NGvi=Nvi=vj∈VG|vivj∈EG, and the degree of vi is dGvi=di=Nvi. Let Kn be the complete graph of order n and G¯ be the complement of the graph G. Let Δ and δ be the maximum degree and the minimum degree of the vertices of G, respectively. The eigenvalues of the adjacency matrix AG, are denoted by λ1G≥λ2G≥…≥λnG. The matrix ℒG=DG−AG, where DG is the diagonal matrix of vertex degrees, is called the Laplacian matrix of G and rarely appears in the literature. The eigenvalues of Laplacian matrix G are denoted as l1G≥l2G≥…≥lnG=0. The Laplacian matrix of a graph and its eigenvalues can be used in several areas of mathematical research and have a physical interpretation in various physical and chemical theories. The adjacency matrix of a graph and its eigenvalues were much more investigated in the past than the Laplacian matrix. Many related physical quantities have the same relation to ℒG; also, there are many problems in physics and chemistry where the Laplacian matrices of graphs and their spectra play the central role. Recently, its applications to several difficult problems in graph theory were discovered (see [1–7]).Merris [8] discussed the Laplacian matrices of graphs. In [9], some bounds are established for Laplacian eigenvalues of graphs. Taheri et al. [10] presented some bounds for the largest Laplacian eigenvalue of graphs. Patra et al. [11] obtained bounds for the Laplacian spectral radius of graphs. In [12], the authors investigated some bounds for the Laplacian spectral radius of an oriented hypergraph. Chen [13] established some bounds for λ1G.In this paper, we first present sharp upper and lower bounds forl1G and ln−1G, and then we investigate the relation between l1G and λ1G.


## 2. Preliminaries

In this section, some fundamental results that are used in this paper are recalled. We begin with the following result, which plays a key role in this section.Lemma 1.
(see [14]). Let G be a graph of order n and size ε. Then,(1)∑i=1n−1li=∑i=1nli=trℒG=2ε,∑i=1n−1li2=∑i=1nli2=trℒ2G=2ε+M1G,where M1G=∑i=1ndi2 is the well-known graph invariant called the first Zagreb index [15].
Favaron and Mahéo [16] proved the following result:Lemma 2.
(see [16]). Let G be a graph of order n. Then,(2)λ1≥∑i=1ndi2n.
The proof of the next result can be found in [17].Lemma 3.
LetG be a graph of order n. Then, l1=l2=…=ln−1 if and only if G≅Kn or G≅K¯n.
Das in [18] proved the following lemma.Lemma 4.
LetG be a connected graph of order n≥3. Then, l2=l3=…=ln−1 if and only if G≅Kn.In [14], a class of real polynomialsPn(x) = xn + a1xn−1 + a2xn−2 + b3xn−3+ … + bn, denoted as Pn(a1, a2), where a1 and a2 are fixed real numbers, was considered.Theorem 1.
For the rootsy1⩾y2⩾…⩾yn of an arbitrary polynomial φny from this class, the following values were introduced:(3)y¯=1n∑i=1nyi,Γ=n∑i=1nyi2−∑i=1nyi2.
Then upper and lower bounds for the polynomial roots,yi,i=1,2,…,n, were determined in terms of the introduced values(4)y¯+1nΓn−1⩽y1⩽y¯+1nn−1Γ,y¯−1ni−1n−i+1Γ⩽yi⩽y¯+1nn−iiΓ,fori=2,3,…,n−1.


## 3. Main Results

In this section, we will obtain some sharp upper and lower bounds forl1G and ln−1G involving the first Zagreb index and order and size of graphs. Moreover, we investigate the relation between l1G and λ1G. The first result is an immediate consequence of Theorem 1 and Lemma 1.Lemma 5.
LetG be a graph of order n≥2 and size ε. Then,(5)2ε+n−12ε+M1G−4ε2/n−2n−1≤l1≤2ε+n−2n−12ε+M1G−4ε2n−1,(6)2ε−n−2n−12ε+M1G−4ε2/2n−1≤ln−1≤2εn−1.
Here, we will obtain a lower and an upper bound for the largest Laplacian eigenvaluel1 and the second smallest Laplacian eigenvalue ln−1, respectively.Theorem 2.
LetG be a graph of order n≥3 and size ε. Then,(7)l1≥2εn−1+1n−1n−22εn−1+2εn−1+∑i=1ndi2,(8)ln−1≤2εn−1−1n−1n−22εn−1+2εn−1+∑i=1ndi2,and the equalities hold if and only if G≅Kn or G≅K¯n.Proof.
For every fixed numbert, we can write that(9)∑i=1n−1li−n−1lt2=∑i=1n−1li−lt2=∑i=1n−1li−lt2+2∑1≤i≤j≤n−1li−ltli−lt.
It is not hard to see that whent=1 or t=n−1, we get(10)∑1≤i≤j≤n−1li−ltli−lt≥0.
Hence, we have(11)∑i=1n−1li−n−1lt2≥∑i=1n−1li−lt2.
So, we can write(12)∑i=1n−1li2−2n−1lt∑i=1n−1li+n−12lt2≥∑i=1n−1li2−2lt∑i=1n−1li+n−1lt.
This is equivalent to(13)lt2−2lt∑i=1n−1lin−1+∑i=1n−1li2n−12−n−1≥∑i=1n−1li2n−12−n−1, or (14)lt−∑i=1n−1lin−12−∑i=1n−1li2n−12+∑i=1n−1li2n−1n−2≥∑i=1n−1li2n−1n−2.
Therefore, we have(15)lt−∑i=1n−1lin−12≥1n−1n−2∑i=1n−1li2−1n−1∑i=1n−1li2.
Hence, by using Lemma1, we have(16)∑i=1n−1li=∑i=1nli=trℒG=2ε,(17)∑i=1n−1li2=∑i=1nli2=trℒ2G=2ε+M1G.
By combining inequalities (15)–(17), we get the following inequality:(18)l1−2εn−12≥1n−1n−22ε−4ε2n−1+∑i=1ndi2.
By inequalities (5) and (6), we have(19)l1−2εn−1≥0,ln−1−2εn−1≤0.
Therefore, we have(20)l1≥2εn−1+1n−1n−22εn−1+2εn−1+∑i=1ndi2ln−1≤2εn−1−1n−1n−22εn−1+2εn−1+∑i=1ndi2.
If the equality in (7) holds, then the inequality in (10) must hold, and hence we have l1=l2=⋯=ln−1=2ε/n−1; thus, by Lemma 3, we have G≅Kn or G≅K¯n. Conversely, if G≅Kn or G≅K¯n, then it is not difficult to see that the equalities in (7) and (8) hold.
Next, we present an upper bound for spectral radius of the Laplacian matrix.Theorem 3.
LetG be a connected graph of order n≥2 and size ε. Then,(21)l1≤16n−162ε+M1Gn−2−4ε2+8ε8n−8.Proof.
Applying Lemma1, we can write(22)β≔∑i=1n−1li2=2ε+∑i=1n−1di2=2ε+M1G,or(23)l12=β−∑i=2n−1li2≤β−1n−2∑i=2n−1li2=β−2ε−l12n−2.
By inequality (23), we have(24)l12≤β−4ε2+l12−4εl1n−2.
Using inequality (24), we get(25)l121+1n−2+4ε2n−2−4εl1n−2−β≤0,or(26)l12n−1+4ε2−4εl1−n−2β≤0.
By inequality (26), we can write(27)l12n−1+4ε2−4εl1−2εn−2−M1Gn−2≤0.
Solving this inequality leads to(28)l1≤16n−162ε+M1Gn−2−4ε2+8ε8n−8.
Finally, we will describe a relationship between spectral radius (l1) of the Laplacian matrix and the spectral radius (λ1) of the adjacency matrix.Theorem 4.
LetG be a connected graph of order n≥3 and size ε. Then,(29)λ1≥l12n−1nn−2+4ε2nn−2−4εl1nn−2−2εn,and the equality holds if and only if G≅Kn.Proof.
By inequality (26) and Lemma 2, we have(30)l12n−1+4ε2−4εl1≤n−2β=n−22ε+∑i=1ndi2,(31)≤n−22ε+nλ12=2εn−2+nn−2λ12.
Now suppose that the equality holds in (29). Then, all the inequalities in the proof must be equalities.
If the equality holds in (30), then inequality (23) must be equality; in other words,(32)β−∑i=2n−1li2=β−1n−2∑i=2n−1li2,or(33)∑i=2n−1li2=1n−2∑i=2n−1li2.
Therefore, by equality (33), we get(34)l2=l3=⋯=ln−1.
Hence, by Lemma4, we get G≅Kn. Conversely, one can easily see that equality holds in (29) when G≅Kn.


## 4. Conclusion

In this paper, we established some sharp upper and lower bounds for the largest eigenvalue and the second smallest eigenvalues of Laplacian matrix involving the first Zagreb index and order and size of graphs. Moreover, we investigate a relation between the largest eigenvalues of Laplacian matrix and the adjacency matrix.There are still open and challenging problems for researchers. For example, the problem ofABC matrix, GA matrix, and so on remains open for further investigation.



---

*Source: 8096874-2021-06-04.xml*