Hovhannes A. Harutyunyan

Sparse Relaxed Broadcast Graphs

The bound $O(n^{1-\epsilon/\alpha})$ on the additional number of edges for $0<\epsilon<\alpha$ is asymptotically tight at the two extremities of the interval $(0,\alpha]", and has implications to the design of graphs with minimum broadcast cost, defined as number of edges times broadcast time.