A while ago I found this equation, not sure where, for determining the number of vertices $v$ given an average "edges per node" $r$ and an average path length $n$. This assumes a DAG where there's one root node and there are no orphans.

$$ v = \frac{r^{t-1}\left(1 - r^n\right)}{1 - r} $$

where $t$ = starting path level (usually 1), $n$ = average path length, and $r$ is average outgoing edges per vertex.

I also figured out how to solve for $n$ using a logarithmic identity, but is it possible to solve for $r$? If I have the average path length and the total number of vertices, can I solve for number of outgoing edges per vertex? I can do it with interpolation and a program, just curious if a derived equation is possible.

  • $\begingroup$ What is an orphan ? $\endgroup$
    – caduk
    Mar 24, 2022 at 8:13
  • $\begingroup$ I was trying to think of a clear way to explain that it's one DAG. The root node has paths to every other node. No other nodes are parentless. $\endgroup$
    – tunesmith
    Mar 25, 2022 at 22:21


You must log in to answer this question.

Browse other questions tagged .