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.

$\endgroup$

2 Answers 2

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.