Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

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