-2
$\begingroup$

I was wondering if there is an upper bound on the total number of fixed-length paths (path length from 1 to $n-1$ given $n$ nodes) in an acyclic graph (not directed) of $n$ nodes? If so, can you point me to some references?

This question explains the counting $s-t$ path is #P-complete but I'm not sure if the same applies to my question as well.

Thanks!

Improve this question
$\endgroup$
8
  • $\begingroup$ You might get some downvotes due to off-topic... $\endgroup$
    – Avi Tal
    May 2, 2021 at 0:05
  • $\begingroup$ Why this is off-topic? $\endgroup$
    – xxks-kkk
    May 2, 2021 at 1:38
  • $\begingroup$ Usually non-research level questions are off topic... The moderators will probably respond soon. $\endgroup$
    – Avi Tal
    May 2, 2021 at 3:56
  • 1
    $\begingroup$ The Computer Science forum is probably the appropriate place. I guess you are right... They should have named the TCS forum as "TCS Research"... $\endgroup$
    – Avi Tal
    May 2, 2021 at 8:17
  • 1
    $\begingroup$ As for “no obvious way”, did you read the first few sentences of cstheory.stackexchange.com/tour, or the faq cstheory.stackexchange.com/help/on-topic it refers to? They both mention research too many times for me to count. $\endgroup$
    – Emil Jeřábek
    May 2, 2021 at 13:43

1 Answer 1

Reset to default
0
$\begingroup$

An undirected acyclic graph is a forest. See here: https://en.wikipedia.org/wiki/Tree_(graph_theory)

So, a rough upper bound would obviously be n^2 since each 2 vertices have at most 1 path between them.

Improve this answer
$\endgroup$

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