A note on connectivity in directed graphs

Abstract

We say a directed graph $G$ on $n$ vertices is irredundant if the removal of any edge reduces the number of ordered pairs of distinct vertices $(u,v)$ such that there exists a directed path from $u$ to $v$. We determine the maximum possible number of edges such a graph can have, for every $n\in \mathbb{N}$. We also characterize the cases of equality. This resolves, in a strong form, a question of Crane and Russell.

4 pages