Sparse hypercube-a minimal k-line broadcast graph

This paper proposes a method for reducing the maximum degree of vertices in graphs that maintain optimal broadcast time when a vertex can call a vertex at distance at most k during any time unit. In the proposed method, we eliminate edges from binary n-cubes. We show that, by this approach, the maximum degree of a vertex can be reduced from n to at most (2 k-1) |k√(n-k)|, where 2⩽k<n, which asymptotically achieves the lower bound for any constant k