2
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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".

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .