论文标题
图形的非背带矩阵的光谱特性
Spectral properties of the non-backtracking matrix of a graph
论文作者
论文摘要
我们研究了图的非背带矩阵的光谱。特别是，我们展示了如何根据较小矩阵的特征向量获得非背带矩阵的特征向量。此外，我们在邻接矩阵的特征值方面找到了非折线矩阵特征值的表达式，并将其用于在非折线矩阵的光谱上，并在频谱上给出下限。我们还研究了可以通过频谱确定的图的特性。具体而言，我们证明组件的数量，度1个顶点的数量以及图形是否为双分部分都取决于非折线矩阵的频谱。
We investigate the spectrum of the non-backtracking matrix of a graph. In particular, we show how to obtain eigenvectors of the non-backtracking matrix in terms of eigenvectors of a smaller matrix. Furthermore, we find an expression for the eigenvalues of the non-backtracking matrix in terms of eigenvalues of the adjacency matrix and use this to upper-bound the spectral radius of the non-backtracking matrix and to give a lower bound on the spectrum. We also investigate properties of a graph that can be determined by the spectrum. Specifically, we prove that the number of components, the number of degree 1 vertices, and whether or not the graph is bipartite are all determined by the spectrum of the non-backtracking matrix.
