Counting Paths in Graphs
| dc.creator | Bartholdi, Laurent | |
| dc.date | 2000-12-18 | |
| dc.date | 2008-06-05 | |
| dc.date.accessioned | 2026-07-07T09:42:43Z | |
| dc.date.available | 2026-07-07T09:42:43Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/math/0012161 | |
| dc.identifier | http://arxiv.org/abs/math/0012161 | |
| dc.identifier | Enseign. Math. 45 (1999) 83-131 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/162285 | |
| dc.subject | Combinatorics | |
| dc.subject | Group Theory | |
| dc.subject | 05A15, 05C38, 47A10 | |
| dc.title | Counting Paths in Graphs | |
| dc.type | text |