-2

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!

xxks-kkk
  • 125
  • 6
  • You might get some downvotes due to off-topic... – Avi Tal May 02 '21 at 00:05
  • Why this is off-topic? – xxks-kkk May 02 '21 at 01:38
  • Usually non-research level questions are off topic... The moderators will probably respond soon. – Avi Tal May 02 '21 at 03:56
  • Thanks for the clarification. That's sad esp. there is no obvious way for me to find out the main purpose of this stack exchange and "theoretical computer science" is subject to interpretation. Should include "research" somewhere in it :( – xxks-kkk May 02 '21 at 07:46
  • 1
    The Computer Science forum is probably the appropriate place. I guess you are right... They should have named the TCS forum as "TCS Research"... – Avi Tal May 02 '21 at 08:17
  • 1
    As for “no obvious way”, did you read the first few sentences of https://cstheory.stackexchange.com/tour, or the faq https://cstheory.stackexchange.com/help/on-topic it refers to? They both mention research too many times for me to count. – Emil Jeřábek May 02 '21 at 13:43
  • It seems you deleted the comments meanwhile, but for the record, let me give a brief answer. This site is no different from any other SE site. Every SE site has a defined scope that determines what questions are on-topic and what are off-topic. A summary is given in a large banner that appears on top of the site whenever you visit the site before creating an account. After that, detailed information about the site can be found under the Help Center icon in the top bar (the ? in a circle); the first link there is the “tour” page. – Emil Jeřábek May 03 '21 at 09:01
  • Great. Thanks for the instruction. It seems like you can keep the comment civil. I think flag your first comment is good enough. – xxks-kkk May 03 '21 at 09:22

1 Answers1

0

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.

Avi Tal
  • 1,606
  • 1
  • 8
  • 13