On the spectrum of the normalized Laplacian for signed graphs: Interlacing, contraction, and replication

We consider the normalized Laplacian matrix for signed graphs and derive interlacing results for its spectrum. In particular, we investigate the effects of several basic graph operations, such as edge removal and addition and vertex contraction, on the Laplacian eigenvalues. We also study vertex replication, whereby a vertex in the graph is duplicated together with its neighboring relations. This operation causes the generation of a Laplacian eigenvalue equal to one. We further generalize to the replication of motifs, i.e. certain small subgraphs, and show that the resulting signed graph has an eigenvalue 1 whenever the motif itself has eigenvalue 1. (C) 2013 Elsevier Inc. All rights reserved.