In the 1990's, Chung [1]} popularised the normalised Laplacian matrix, sometimes defined by \(\mathcal {L}_G=D_G^{-1}L_G\) , which has connections to random walks as \(\mathcal {L}_G = I-D_G^{-1}A_G\)  where \(D_G^{-1}A_G\)  is the random walk matrix. The combinatorial and normalised Laplacians may be viewed as discrete analogues of the (negative) Laplace-Beltrami operator on Riemannian manifolds, defined by the negative divergence of the gradient, and this connection has been used to relate the second combinatorial and normalised Laplacian eigenvalues of a graph to sparse (normalised) cuts [1]}, [3]}, giving a discrete analogue of Cheeger's isoperimetric inequality in Riemannian geometry [4]}. In addition, combinatorial and normalised Laplacian eigenvalues can be used to obtain bounds on various parameters of a graph, including its chromatic number [1]}, [6]}, diameter [1]}, [8]} and independence number [9]}.
