The number of reachable pairs in a digraph (Q5920601)

Let \(R(G)\) be the number of ordered pairs \((u, v)\) of vertices of a digraph \(G\), where \(u\) and \(v\) are distinct, such that \(v\) is reachable from \(u\). Likewise, let \(R(k, G)\) be a number such that \(v\) is reachable from \(u\) by a path of length less than \(k + 1\). The paper studies the range \(S(n)\) of \(R(G)\) and the range \(S(k, n)\) of \(R(k, G)\) over all digraphs on \(n\) vertices. It gives a sufficient condition and a necessary condition for an integer to belong to \(S(n)\). It also determines the set \(S(n)\) for all \(n < 209\) and \(S(k, n)\) for all \(k < 5\).