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.