On the number of reachable pairs in a digraph

A pair $(u,v)$ of (not necessarily distinct) vertices in a directed graph $D$ is called a reachable pair if there exists a directed path from $u$ to $v$. We define the weight of $D$ to be the number of reachable pairs of $D$, which equals the sum of the number of vertices in $D$ and the number of directed edges in the transitive closure of $D$. In this paper, we study the set $W(n)$ of possible weights of directed graphs on $n$ labeled vertices. We prove that $W(n)$ can be determined recursively and describe the integers in the set. Moreover, if $b(n)⩾n$ is the least integer for which there is no digraph on $n$ vertices with exactly $b(n)+1$ reachable pairs, we determine $b(n)$ exactly through a simple recursive formula and find an explicit function $g(n)$ such that $\mathrm{\mid }b(n)-g(n)\mathrm{\mid }<2n$ for all $n⩾3$. Using these results, we are able to approximate $\mathrm{\mid }W(n)\mathrm{\mid }$ – which is quadratic in $n$ – with an explicit function that is within $30n$ of $\mathrm{\mid }W(n)\mathrm{\mid }$ for all $n \geqslant 3$,thusansweringaquestionofRao\mathrm{.}Sincetheweightofadirectedgraphon$n$verticescorrespondstothenumberofelementsinapreorderonan$n$ element set and the number of containments among the minimal open sets of a topology on an $n$ point space, our theorems are applicable to preorders and topologies.