On the monotonicity of the broadcast function

AbstractThe broadcast function, B(n), is the minimum number of edges in any graph on n vertices such that each vertex can broadcast in time ⌈logn⌉. It is a long-standing conjecture that B(n) is non-decreasing for n in the range 2m−1+1⩽n⩽2m. We show that the conjecture holds for n in the range 2m−1+1⩽n⩽2m−1+2m−3. Our investigation produces a similar result for k-broadcasting, a variant of broadcasting in which an informed vertex can call up to k of its neighbors in each time unit. Along the way, we give a method to construct k-broadcast graphs, those graphs which allow minimum time k-broadcasting from each vertex for certain values of n and give some new results on t-relaxed k-broadcast graphs—those graphs which allow k-broadcasting from each vertex in minimum +t time units