MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Bounds on number of simple paths in graph

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.

-

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.

-

I would comment if I could, but since I can't, it goes as an answer.

The keyword you are looking for in Property 3 is "Induced Path".

-