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

Atay F. M., Tuncel H.

LINEAR ALGEBRA AND ITS APPLICATIONS, cilt.442, ss.165-177, 2014 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 442
  • Basım Tarihi: 2014
  • Doi Numarası: 10.1016/j.laa.2013.08.022
  • Dergi Adı: LINEAR ALGEBRA AND ITS APPLICATIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.165-177
  • Anahtar Kelimeler: Signed graph, Interlacing, Normalized Laplacian, Contraction, Replication, Duplication, EIGENVALUES, SYNCHRONIZATION, NETWORKS, PROOF
  • Dokuz Eylül Üniversitesi Adresli: Hayır

Özet

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.