THE LAPLACIAN SPECTRUM OF GRAPHS y

Abstract

The paper is essentially a survey of known results about the spectrum of the Laplacian matrix of graphs with special emphasis on the second smallest Lapla- cian eigenvalue 2 and its relation to numerous graph invariants, including connectivity, expanding properties, isoperimetric number, maximum cut, independence number, genus, diameter, mean distance, and bandwidth-type parameters of a graph. Some new results and generalizations are added.