Page 121 - Textos de Matemática Vol. 39

OBSERVATIONS CONCERNING SPLIT GRAPHS 111
First Infinite Family of Self Complementary Split Graphs: Let Γn=(V,E) be the graph with vertex set V = W ∪U and edge set E = W(2) ∪{uiwi+t : 0 ≤ t < q,1 ≤ i ≤ 2q}, where W(2) is the set of all C(2q,2) pairs of vertices of W , and “i + t” is understood modulo 2q. Because W is a clique and U an independent set, Γn is a split graph. Observing that the degree of ui, resp. wi, inΓn isq,resp.3q−1,1≤i≤2q,onededucesthatthenumberofedgesin the graph Γn is
o(E) = q(4q − 1) = n(n − 1)/4 = C(n,2)/2,
half the number of the number of edges of Kn. Verification that Γn ∼= Γcn is left to the reader.
Second Infinite Family of Self Complementary Split Graphs: With n, U, V, and W as in the first family, define Ψn = (V,F), where F = W(2) ∪{uiwj : 1≤j≤q,1≤i≤q}∪{uiwj :q<j≤2q,q<i≤2q}.ThatΨn isaself complementary split graph is left to the reader. In the case that q = 1, Ψ4 and Γ4 are both isomorphic to the path, P4. A proof that Ψn Γn, q > 1, can be found in the next section.
Two infinite families of self complementary split graphs on n = 4q + 1 vertices can be obtained by modifying Ψn and Γn as follows: Let V ′ = V ∪ {v}, wherev∈/V,E′ =E∪Q,F′ =F∪Q,andQ={vwi :1≤i≤2q}.
4. The Laplacian Spectrum.
Suppose G = (V,E) is a graph with vertex set V = {v1,v2,...,vn}. Let D(G) = diag(dG(v1), dG(v2), . . . , dG(vn)) be the diagonal matrix of its vertex degrees. The n × n Laplacian matrix L(G) = D(G) − A(G), where A(G) is the usual (0,1)-adjacency matrix. Recall that L(G) is positive semidefinite with rank n − c, where c is the number of components of G. The spectrum of L(G) is denoted s(G)=(λ1(G),λ2(G),...,λn(G)), where λ1(G)≥λ2(G)≥...≥λn(G)=0. Following M. Fiedler (see, e.g., [3]), we identify each eigenvector x of L(G) with thefunctionx:V →Rdefinedbyx(vi)=xi,1≤i≤n.
A Faria cluster in G is a set of two or more independent vertices each with the same set of neighbors. If {u1,u2,...,ur} is a Faria cluster in G of cardinality r and (common) degree d, then yj : V → R defined by yj(u1) = −1, yj(uj) = 1, and yj(v) = 0 for all v ∈ V \ {u1,uj}, is an eigenvector affording λ=d,1<j≤r.Because{yj :1<j≤r}islinearlyindependent,itfollows that the multiplicity of λ = d as an eigenvalue of L(G) is not less than r − 1 [2].
Observing that, for q > 1, the self complementary split graph Ψn has two Faria clusters of cardinality and degree q, while Γn has none, proves that Ψn Γn, n = 4q ≥ 8. The same observation shows that the spectrum of Ψn