Counting Paths in Graphs
Counting Paths in Graphs
复制标题
DOI：
--
复制
发表时间：
2000-12
期刊：
影响因子：
--
通讯作者：
L. Bartholdi
中科院分区：
文献类型：
--
作者：
L. Bartholdi
我们给出了一个公式的简单组合证明，该公式扩展了 Grigorchuk（由 Cohen 重新发现）关于随机游走的共生和谱半径的结果。我们的主要结果是一个明确的方程，确定图中路径上“颠簸”的数量：在 $d$-正则（不一定传递）无向图中，让系列 $G(t)$ 计算两个固定点之间的所有路径，按其长度 $t^{length}$ 进行加权，$F(u,t)$ 计算相同的路径，加权为 $u^{颠簸数量}t^{length}$。那么就有 $$F(1-u,t)/(1-u^2t^2) = G(t/(1+u(d-u)t^2))/(1+u(d-u)t^2)。$$ 然后我们推导出图的“自由乘积”和“直接乘积”的电路级数。我们还获得了 Ihara-Selberg zeta 函数的广义形式。
We give a simple combinatorial proof of a formula that extends a result by Grigorchuk (rediscovered by Cohen) relating cogrowth and spectral radius of random walks. Our main result is an explicit equation determining the number of `bumps' on paths in a graph: in a $d$-regular (not necessarily transitive) non-oriented graph let the series $G(t)$ count all paths between two fixed points weighted by their length $t^{length}$, and $F(u,t)$ count the same paths, weighted as $u^{number of bumps}t^{length}$. Then one has $$F(1-u,t)/(1-u^2t^2) = G(t/(1+u(d-u)t^2))/(1+u(d-u)t^2).$$ We then derive the circuit series of `free products' and `direct products' of graphs. We also obtain a generalized form of the Ihara-Selberg zeta function.