Eigenvalues of normalized Laplacian matrix of graphs References

Eigenvalues of normalized Laplacian matrix of graphs
Shaowei Sun and Kinkar Ch. Das
Department of Mathematics, Sungkyunkwan University,
Suwon 440-746, Republic of Korea
E-mail: [email protected], [email protected]
Abstract
Let G be a graph with vertex set V (G) = {v1 , v2 , . . . , vn } and edge set E(G).
Also let di be the degree of vertex vi ∈ V (G). The normalized Laplacian matrix of
the graph G is denoted by L(G) = (Lij ) and is deﬁned by


if i = j and di ̸= 0
1

1
Lij = − √di dj if vi vj ∈ E(G)


0
otherwise.
In this talk, we discuss some bounds on the largest normalized Laplacian eigenvalue of graph G in terms of graph parameters. Moreover, we give the results on the
normalized Laplacian eigenvalues of graph G. Finally, we present some results of
the eﬀect on the largest and the second smallest normalized Laplacian eigenvalues
by grafting edges.
Key Words: Normalized Laplacian matrix, Normalized Laplacian eigenvalues, Triangulation, Maximal Planar graph, Covering number
References
[1] Li, H.-H., Li, J.-S., Fan, Y.-Z. Fan., The eﬀect on the second smallest eigenvalue of
the normalized Laplacian of a graph by grafting edges, Linear Multilinear Algebra
50(6) (2008) 627-638.
[2] Chung, F. R. K., Spectral graph theory. American Mathematical Soc., 1997.
1
[3] Cavers, M., The normalized Laplacian matrix and general Randic index of graphs.
PhD dissertation, University of Regina, 2010.
[4] Chen, H., Jost, J., Minimum vertex covers and the spectrum of the normalized
Laplacian on trees. Linear Algebra Appl. 437 (2012) 1089–1101.
[5] Das, K. C., G¨
ung¨or, A. D., Bozkurt, S¸. B., On the normalized Laplacian eigenvalues
of graphs, Ars Combinatorica, in press.
[6] Li, J., Guo, J.-M., Shiu, W. C., Chang, A., An edge-separating theorem on the
second smallest normalized Laplacian eigenvalue of a graph and its applications,
Discrete Appl. Math. 171 (2014) 104–115.
2

Download Report