Sparse Hypercube—a minimal k-line broadcast graph Original Research Article

This paper proposes methods 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. The basic idea behind the proposed construction method is to eliminate edges from binary n-cubes. We show that, by this approach, the maximum degree of a vertex can be reduced to at most (2k−1)⌈log2 |V|−kk⌉, where 2⩽k