Bounds on number of simple paths in graph - MathOverflow 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 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 Answer by Gerhard Paseman for Bounds on number of simple paths in graph 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 Answer by Vinicius dos Santos for Bounds on number of simple paths in graph 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>