Graphs with integer normalized Laplacian eigenvalues

Let {V} be the vertex set of a graph; all graphs here are assumed connected. Write {u\sim v} if {u, v} are adjacent vertices. The Laplacian of a function {f\colon V\to \mathbb R} is defined as {L f(v) = \sum_{u\colon u\sim v}(f(v)-f(u))}. Its properties were discussed earlier in Laplacian spectrum of small graphs.

The normalized Laplacian involves the vertex degree {d_v} (the number of vertices adjacent to {v}). It is defined by

{\displaystyle L_N f(v) = \frac{1}{\sqrt{d_v}}\sum_{u\colon u\sim v}\left( \frac{f(v)}{\sqrt{d_v}} - \frac{f(u)}{\sqrt{d_u}} \right)}

The matrix of {L_N} is obtained by multiplying the matrix of {L} on both sides by the diagonal matrix with {1/\sqrt{d_v}} on the diagonal. Hence, {L_N} is also positive semidefinite and has the same rank as {L}. In particular, it has a simple eigenvalue 0 and the rest of eigenvalues are positive. Let us write {\mu_1 \le \cdots \le \mu_n} for the eigenvalues of {L_N}. In this notation, {\mu_1= 0} and {\mu_k>0} for {k\ge 2}.

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 {L_N} has {1} in every diagonal entry. Its off-diagonal entries are {-1/\sqrt{d_ud_v}} if {u\sim v}, and {0} otherwise. Since the trace is {n}, and there are {n-1} positive eigenvalues, the way that a normalized Laplacian spectrum can consist of integers is {(0, 1, \ldots, 1, 2)}.

It turns out that the largest normalized Laplacian eigenvalue {\mu_n} equal to {2} if and only if the graph is bipartite; otherwise it is less than {2} (as a reminder, all graphs are assumed connected in this post). Indeed, {\mu_n} is the norm of {L_N}, which is the supremum of {\langle L_N f, f\rangle/ \langle f, f\rangle} over all functions {f}. A computation shows {\langle L_N f, f\rangle = \sum_E (f(u)/\sqrt{d_u} - f(v) / \sqrt{d_v})^2} where the sum is taken over the edge set {E}: each edge contributes one term to the sum, with {u, v} being its endpoints. The sum becomes simpler if we write {f(v)=\sqrt{d_v} g(v)}; after this substitution,

{\displaystyle \mu_n = \sup_g \frac{\sum_E (g(u)-g(v))^2 }{\sum_V g(v)^2 d_v}}

The denominator can be rewritten as a sum over edges, namely {\sum_E (g(u)^2 + g(v)^2) }. This shows that the introduction of vertex degree into the denominator achieves certain symmetry: each value of {f} appears in the numerator as many times as in the denominator.

Since {(g(u)-g(v))^2 \le 2(g(u)^2 + g(v)^2)}, the numerator is at most {2 \sum_E (g(u)^2 + g(v)^2)}. Thus {\mu_n\le 2}, and to achieve equality here we need {g(u) + g(v) = 0} whenever {u\sim v}. This requires {|g|} to be constant and the graph to be bipartite, its 2-coloring provided by {\mathrm{sign}\,g}. Conversely, any 2-coloring of a graph provides us with a function {g\colon V\to \{-1, 1\}} for which {\sum_E (g(u)-g(v))^2 = 2\sum_V g(v)^2 d_v} according to the above.

To achieve integer spectrum, we also need {1} to be an eigenvalue of multiplicity {n-2} for {L_N}, which is equivalent to {\mathrm{rank}\,(I-L_N) = 2}. Since the graph is bipartite, {I-L_N} has the block form

{\displaystyle I - L_N = \begin{pmatrix} 0 & A \\ A^t & 0\end{pmatrix}}

where the (possibly rectangular) block {A} has entries {1/\sqrt{d_u d_v}} corresponding to {u\sim v}. In order for {I-L_N} to have rank 2, the matrix {A} must have rank 1. Any zero entry of a rank-1 matrix lies in a zero row, but {A} cannot have a zero row because the graph is connected. Thus, all entries of {A} are positive, which means we have a complete bipartite graph.

The converse is immediate: for a complete bipartite graph {K_{p, q}} the matrix {A} has all entries equal to {1/\sqrt{pq}}, hence its rank is 1.

As a final remark, the ordinary (un-normalized) Laplacian of a complete bipartite graph {K_{p, q}} also has integer eigenvalues. Indeed, the complement of {K_{p, q}} is the disjoint union of complete graphs {K_p} and {K_q}, with the spectra {(0, p, \ldots, p)} and {(0, q, \ldots, q)}. Passing to the complement means replacing each eigenvalue {\lambda} by {n-\lambda}, except that one {0} stays {0} (this is discussed in Laplacian spectrum of small graphs). Hence, the Laplacian spectrum of {K_{p, q}} consists of: simple eigenvalues {0} and {n}, eigenvalue {p} of multiplicity {q-1}, and eigenvalue {q} of multiplicity {p-1}. Worth noting that the Laplacian spectrum determines a complete bipartite graph up to an isomorphism, while the normalized Laplacian spectrum does not.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.