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.



Bounds on number of simple paths in graph
If the distance from s to t is 1, or the max degree is 2, then there are at most 2 such paths. Otherwise there are potentially exponentially many such paths even among cubic graphs (think of a cycle of diamonds). Of course, I am considering the extreme case and not looking at forests or other classes of graphs with few cycles. You may get a better answer if you know things like the girth of the graph and the cycle count and arrangement.


Gerhard "Ask Me About System Design" Paseman, 2012.01.11


