Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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