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
26/2021
The Perron non-backtracking eigenvalue after node addition
Consider a finite undirected unweighted graph G and add a new node to it arbitrarily connecting it to pre-existing nodes. We study the behavior of the Perron eigenvalue of the non-backtracking matrix of G before and after such a node addition. We prove an interlacing-type result for said eigenvalue, namely, the Perron eigenvalue never decreases after node addition. Furthermore, our methods lead to bounds for the difference between the eigenvalue before and after node addition. These are the first known bounds that have been established in full rigor. Our results depend on the assumption of diagonalizability of the non-backtracking matrix. Practical experience says that this assumption is fairly mild in many families of graphs, though necessary and sufficient conditions for it remain an open question.
