I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My result works on any bounded degree locally finite graph, and I'd like to discuss the analogy to random walks there as well. Unfortunately, I've never studied random walks on graphs other than lattices. It's easy to define a random walk on an arbitrary locally finite graph (if there are $d$ edges out of $v$ then assign each probability $1/d$). Let's assume a very standard hypothesis: there is a fixed $D<\infty$ s.t. the degree of each vertex is less than $D$

One thing which is known is Doyle and Snell's Theorem: if $G$ can be drawn in a civilized manner (i.e. the lengths of all edges are between $a$ and $b$ where $0< a,b < \infty$) in $\mathbb{R}$ or $\mathbb{R}^2$ then the simple random walk on $G$ is recurrent.

Unfortunately, this leaves the question open for graphs which can't be drawn this way. An exercise in Doyle and Snell asks you to find a graph which can't be drawn this way but which is still recurrent. There is some discussion which basically says if a graph can be drawn in a civilized manner in $\mathbb{R}^3$ and also satisfies another property about the $k$-fuzz of $G$ then it's transient. The rest of their paper gets heavily into the language of flows and I don't really understand it. It doesn't seem to finish the classification.

What's the current state of knowledge on recurrence vs. transience for random walks on a bounded degree locally finite graph? Has anyone figured this out for graphs other than those studied by the papers mentioned here?

I also found a paper by Carsten Thomassen which basically says if a graph grows slower than $\mathbb{Z}^2$ then it's recurrent (due to Nash-Williams originally) and if it satisfies an isoperimetric inequality slightly stronger than that of $\mathbb{Z}^2$ then it's transient. I don't understand this paper at all, but I'd be curious to know if it covers a larger class of graphs than Doyle and Snell's results do.