Characterization of Graph Laplacians

Question

It is known that every graph Laplacian (of a simple undirected graph) is a positive semi-definite matrix. However, is every positive definite matrix a graph Laplacian?

Answer 1

There are two more conditions on a matrix $g\in M_n(\mathbb{R})$ besides positive-semidefiniteness: The off-diagonal entries have to be nonpositive, and all the rows and columns have to sum to $0$. (In particular, $0$ is an eigenvalue of $g$.) If those two conditions hold, then $g$ is the Laplacian of the graph $\Gamma$ with vertex set $V(\Gamma) = \{1, \dots, n\}$, edges connecting those distinct $i, j\in V(\Gamma)$ with $g_{ij}\not = 0$, and weights $w_{ij} = -g_{ij}$.

That's assuming you're referring to the Laplacian of a weighted graph. Otherwise, there are obvious integrality conditions to enforce.

Answer 2

No. The Laplacian of a simple undirected graph always has an eigenvalue equal to zero.

Observe that the sum of every row of the Laplacian is equal to zero. Thus, the vector of ones is an eigenvector with eigenvalue zero.