Page 122 - Textos de Matemática Vol. 39

112 RUSSELL MERRIS
contains λ = q as an eigenvalue with multiplicity not less than 2(q − 1). Indeed, as the reader may verify, λ = 2 is an eigenvalue of Ψ8 with multiplicity exactly 2. In fact, though not guaranteed by any Faria clusters, λ = 2 is a (simple) eigenvalue of Γ8 with eigenvector x defined by the following variation on Faria’s construction: x(wi)=0, 1≤i≤4, x(u1)=x(u3)=1, and x(u2)=x(u4)=−1.
For any graph G on n vertices, L(G) + L(Gc) = nIn − Jn, where In is the identity matrix and Jn is the n × n matrix each of whose entries is 1. It follows from this observation and the fact that the row sums of L(G) are zero, that s(Gc) = (n−λn−1(G),...,n−λ1(G),0). In particular, since Ψn ∼= Ψcn, λ = 3q is also an eigenvalue of Ψn with multiplicity not less than 2(q − 1).
Finally,itiseasytoseethatx:V →Rdefinedbyx(ui)=1and x(wi) = −1, 1 ≤ i ≤ 2q, is an eigenvector affording λ = 2q for both L(Ψn) and L(Γn). Together with λ = 0, this shows that at least n − 2 of the eigenvalues of Ψn are integers. Indeed,
det(xI8 − L(Ψ8)) = x(x − 2)2(x − 4)(x − 6)2(x2 − 8x + 8).
If integer eigenvalues are desirable, then Γn is less obliging, as are the minimal split graphs. Indeed, apart from λ = 0, only the semiregular minimal split graphs reliably yield even a second integer eigenvalue. Suppose G = (V, E) is a hairy clique. Let V = W ∪U be the partition of V into a clique of size o(W) = r and an independent set U of degree 1 vertices. Suppose each vertex w ∈ W is adjacent to exactly p vertices of U (so that n = o(V ) = r(p + 1)). Define x:V →Rbyx(w)=p,w∈W,andx(u)=−1,u∈U.Itiseasilyconfirmed that x is an eigenvector of L(G) corresponding to λ = p + 1. (When p = 1 and λ = 2, this observation is contained in [10, Theorem 1]. Also see [4] and [15].)
5. Open Questions.
Given that threshold graphs are Laplacian integral (i.e., the Laplacian spectra of threshold graphs consist entirely of integers [11]), it seems natural to look for similar behavior among “nearby” graphs.
Problem 1. Prove or disprove the existence of a nonthreshold, Laplacian integral split graph.
The difficulty may lie with P4, an induced subgraph of every nonthreshold split graph and, itself, a minimal split graph. Roughly speaking, a decomposable graph (or cograph) is one that can be “constructed” from isolated vertices using unions and complements. Every threshold graph is decomposable and every decomposable graph is Laplacian integral, but G is decomposable if and only if no induced subgraph of G is isomorphic to P4.