Estimating distance between an eigenvalue of a signed graph and the spectrum of an induced subgraph

Abstract

The distance between an eigenvalue λ of a signed graph Ġ and the spectrum of a signed graph Ḣ is defined as min{|λ−μ|:μis an eigenvalue ofḢ}. In this paper, we investigate this distance when Ḣ is a largest induced subgraph of Ġ that does not have λ as an eigenvalue. We estimate the distance in terms of eigenvectors and structural parameters related to vertex degrees. For example, we show that |λ||λ−μ|≤δĠ∖Ḣmax{dḢ(i)dĠ−V(Ḣ)(j):i∈V(Ġ)∖V(Ḣ),j∈V(Ḣ),i∼j}, where δĠ∖Ḣ is the minimum vertex degree in V(Ġ)∖V(Ḣ). If Ḣ is obtained by deleting a single vertex i, this bound reduces to |λ||λ−μ|≤d(i). We also consider the case in which λ is a simple eigenvalue and Ḣ is not necessarily a vertex-deleted subgraph, and the case when λ is the largest eigenvalue of an ordinary (unsigned) graph. Our results for signed graphs apply to ordinary graphs. They can be interesting in the context of eigenvalue distribution, eigenvalue location or spectral distances of (signed) graphs.