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

Fatihcan M. Atay and Hande Tuncel

Contact the author: Please use for correspondence this email.
Submission date: 31. May. 2013
Pages: 17
published in: Linear algebra and its applications, 442 (2014), p. 165-177 
DOI number (of the published article): 10.1016/j.laa.2013.08.022
Bibtex
MSC-Numbers: 05C50, 05C22, 15A18, 05C76
Keywords and phrases: Signed graph, interlacing, normalized Laplacian, contraction, replication, dominating set
Download full preprint: PDF (363 kB)

Abstract:
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.