Improved upper and lower bounds for k-broadcasting

We continue the investigation of k-broadcasting, a variant of broadcasting in which an informed vertex can call up to k of its neighbors in each time unit. A focus of the investigation into broadcasting is the function B-k(n) , which is the minimum number of edges in any n vertex graph such that each vertex can originate a k-broadcast that completes in minimum time. We give several methods to construct graphs which allow minimum-time k-broadcastin g from each vertex. These constructions give improvements to the best curre nt upper bounds on B-k(n). We also give an improvement to the best existing lower bound on Bk(n). In addition, a few new exact values of B-k(n) are de termined. (C) 2001 John Wiley & Sons, Inc.