Sparse Hypercubea minimal k-line broadcast graph ?
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 , where , which asymptotically achieves the lower bound provided |V|=2n and a constant k.
minimal broadcast graph k-line communication sparse hypercube