Mathematics – Combinatorics
Scientific paper
2000-12-18
Enseign. Math. 45 (1999) 83-131
Mathematics
Combinatorics
Scientific paper
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.
No associations
LandOfFree
Counting Paths in Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counting Paths in Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Paths in Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-180973