Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint
52/2013

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

Fatihcan M. Atay and Hande Tuncel

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.

Received:
May 31, 2013
Published:
Jun 3, 2013
MSC Codes:
05C50, 05C22, 15A18, 05C76
Keywords:
Signed graph, interlacing, normalized Laplacian, contraction, replication, dominating set

Related publications

inJournal
2014 Repository Open Access
Fatihcan M. Atay and Hande Tuncel

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

In: Linear algebra and its applications, 442 (2014), pp. 165-177