Let be the vertex set of a graph; all graphs here are assumed connected. Write if are adjacent vertices. The Laplacian of a function is defined as . Its properties were discussed earlier in Laplacian spectrum of small graphs.
The normalized Laplacian involves the vertex degree (the number of vertices adjacent to ). It is defined by
The matrix of is obtained by multiplying the matrix of on both sides by the diagonal matrix with on the diagonal. Hence, is also positive semidefinite and has the same rank as . In particular, it has a simple eigenvalue 0 and the rest of eigenvalues are positive. Let us write for the eigenvalues of . In this notation, and for .
There are many graphs with integer Laplacian eigenvalues; they do not seem to follow any particular pattern. In contrast, the graphs with integer normalized Laplacian eigenvalues have a simple description.
The matrix of normalized Laplacian has in every diagonal entry. Its off-diagonal entries are if , and otherwise. Since the trace is , and there are positive eigenvalues, the way that a normalized Laplacian spectrum can consist of integers is .
It turns out that the largest normalized Laplacian eigenvalue equal to if and only if the graph is bipartite; otherwise it is less than (as a reminder, all graphs are assumed connected in this post). Indeed, is the norm of , which is the supremum of over all functions . A computation shows where the sum is taken over the edge set : each edge contributes one term to the sum, with being its endpoints. The sum becomes simpler if we write ; after this substitution,
The denominator can be rewritten as a sum over edges, namely . This shows that the introduction of vertex degree into the denominator achieves certain symmetry: each value of appears in the numerator as many times as in the denominator.
Since , the numerator is at most . Thus , and to achieve equality here we need whenever . This requires to be constant and the graph to be bipartite, its 2-coloring provided by . Conversely, any 2-coloring of a graph provides us with a function for which according to the above.
To achieve integer spectrum, we also need to be an eigenvalue of multiplicity for , which is equivalent to . Since the graph is bipartite, has the block form
where the (possibly rectangular) block has entries corresponding to . In order for to have rank 2, the matrix must have rank 1. Any zero entry of a rank-1 matrix lies in a zero row, but cannot have a zero row because the graph is connected. Thus, all entries of are positive, which means we have a complete bipartite graph.
The converse is immediate: for a complete bipartite graph the matrix has all entries equal to , hence its rank is 1.
As a final remark, the ordinary (un-normalized) Laplacian of a complete bipartite graph also has integer eigenvalues. Indeed, the complement of is the disjoint union of complete graphs and , with the spectra and . Passing to the complement means replacing each eigenvalue by , except that one stays (this is discussed in Laplacian spectrum of small graphs). Hence, the Laplacian spectrum of consists of: simple eigenvalues and , eigenvalue of multiplicity , and eigenvalue of multiplicity . Worth noting that the Laplacian spectrum determines a complete bipartite graph up to an isomorphism, while the normalized Laplacian spectrum does not.