The Laplacian matrix is the representation of a graph in matrix form.
Consider a simple graph $G$. Given its degree matrix $D$, and adjacency matrix $A$, the Laplacian is defined as
$$L = D - A$$
with all matrices having size $|G| \times |G|$.
The degree matrix $D$ consists only of entries in the diagonal, with $D_{i,i}$ representing the degree of node $i$. The adjacency matrix has entries $A_{i,j} = 1$ when there is an edge in $G$ from $i$ to $j$. These entries could also be used to represent edge weight in the case of a weighted graph, or the number of edges in the case of a multigraph. If the graph is undirected, the matrix will be symmetric.
The eigenvalues and eigenvectors of the Laplacian provide a rich amount of information about the properties of a graph, this is the field of Spectral Graph Theory. In particular, the number of connected components in the graph is equal to the multiplicity of the zero eigenvalue. The second smallest eigenvalue (also called Fiedler Value) is useful for graph partitioning and linear arrangement problems.
