On the spectrum of the normalized Laplacian for signed graphs: Interlacing, contraction, and replication
LINEAR ALGEBRA AND ITS APPLICATIONS, vol.442, pp.165-177, 2014 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Volume: 442
- Publication Date: 2014
- Doi Number: 10.1016/j.laa.2013.08.022
- Journal Name: LINEAR ALGEBRA AND ITS APPLICATIONS
- Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Page Numbers: pp.165-177
- Keywords: Signed graph, Interlacing, Normalized Laplacian, Contraction, Replication, Duplication
- Dokuz Eylül University Affiliated: No
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. (C) 2013 Elsevier Inc. All rights reserved.