Spectral deviations of graphs

Abstract

For the graphs $G$ and $H$ , the spectral deviation of $H$ from $G$ is defined as $$\rho_G(H)=\sum_{\mu \in H}min_{\lambda \in G} \lvert \lambda−\mu \rvert$$, where $\in$ designates that the given number is an eigenvalue of the adjacency matrix of the corresponding graph. In this study, we consider the problem of existence of a proper induced subgraph $H$ of a prescribed graph $G$ such that $\rho_G(H)=0$ , and the problem of determination of all such subgraphs. We investigate these problems in the framework of Smith graphs and their induced subgraphs, graphs with small second largest eigenvalue, graphs with small number of either positive or distinct eigenvalues, integral graphs, and chain graphs. Our results can be interesting in the context of graphs with a fixed number of distinct eigenvalues, eigenvalue distribution, or spectral distances of graphs.