On the Radius of Nonsplit Graphs and Information Dissemination in Dynamic Networks

Matthias Függer, Thomas Nowak, Kyrill Winkler

A nonsplit graph is a directed graph where each pair of nodes has a common incoming neighbor. We show that the radius of such graphs is in $O(\log \log n)$, where $n$ is the number…