Given an undirected graph $G$ and vertices $s, t$, are there any upper bounds on the number of simple paths from $s$ to $t$?
Can these bounds be improved if you know
1) The distance from $s$ to $t$
2) The graph has max degree $\Delta$
3) No two non-adjacent vertices on the path are allowed to be neighbors. For example if $x, y, z$ is a path, and $x$ is a neighbor of $z$, we would disallow that path
I tried looking on Google but I don't know what the keyword would be. Any pointers to papers or keywords would be great!
Thanks for the help.