most recent 30 from http://mathoverflow.net 2013-06-20T05:19:44Z http://mathoverflow.net/feeds/question/85433 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85433/bounds-on-number-of-simple-paths-in-graph David Harris 2012-01-11T18:07:23Z 2012-02-02T03:29:09Z

<p>Given an undirected graph $G$ and vertices $s, t$, are there any upper bounds on the number of simple paths from $s$ to $t$?</p> <p>Can these bounds be improved if you know</p> <p>1) The distance from $s$ to $t$</p> <p>2) The graph has max degree $\Delta$</p> <p>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</p> <p>I tried looking on Google but I don't know what the keyword would be. Any pointers to papers or keywords would be great!</p> <p>Thanks for the help.</p>

http://mathoverflow.net/questions/85433/bounds-on-number-of-simple-paths-in-graph/85437#85437 Gerhard Paseman 2012-01-11T18:25:21Z 2012-01-11T18:25:21Z

<p>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.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2012.01.11</p>

http://mathoverflow.net/questions/85433/bounds-on-number-of-simple-paths-in-graph/87302#87302 Vinicius dos Santos 2012-02-02T03:29:09Z 2012-02-02T03:29:09Z

<p>I would comment if I could, but since I can't, it goes as an answer.</p> <p>The keyword you are looking for in Property 3 is "<a href="http://en.wikipedia.org/wiki/Induced_path" rel="nofollow">Induced Path</a>".</p>