The Perron non-backtracking eigenvalue after node addition

Leo Torres

Contact the author: Please use for correspondence this email.
Submission date: 18. Nov. 2021
Bibtex
MSC-Numbers: 05C50, 05C82, 15A18, 15B99
Keywords and phrases: Spectral graph theory, non-backtracking, interlacing
Link to arXiv: See the arXiv entry of this preprint.

Abstract:
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.