A Combinatorial Proof of Ihara-Bass's Formula for the Zeta Function of Regular Graphs
A Combinatorial Proof of Ihara-Bass's Formula for the Zeta Function of Regular Graphs
复制标题
正则图Zeta函数Ihara-Bass公式的组合证明
DOI：
10.4230/lipics.fsttcs.2017.46
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Bharatram Rangarajan
中科院分区：
文献类型：
--
作者：
Bharatram Rangarajan
给出了有限正则图的Zeta函数的Bass行列式公式的一个初等组合证明。这是通过在图的邻接算子的特征值中用切比雪夫多项式来表示给定长度的非回溯圈的数目来实现的。一个独立有趣的相关观察是，正则图的Ramanujan性质等价于每个长度的非回溯圈的数目的紧界。
We give an elementary combinatorial proof of Bass's determinant formula for the zeta function of a finite regular graph. This is done by expressing the number of non-backtracking cycles of a given length in terms of Chebyshev polynomials in the eigenvalues of the adjacency operator of the graph. A related observation of independent interest is that the Ramanujan property of a regular graph is equivalent to tight bounds on the number of non-backtracking cycles of every length.