On time-relaxed broadcasting networks

Given a communication network (modelled as a graph), a message is transmitted to at one vertex transmits to all other vertices in such a way that each message transmission takes one time unit and each vertex participates in at most one transmission to its neighbor per time step. We call this process broadcasting. For t≥0t≥0, let Bt(n)Bt(n) be the number of edges in the sparsest possible graph on nn vertices in which broadcasting can be accomplished in ⌈log2n⌉+t⌈log2n⌉+t steps regardless of the originator. Shastri [A. Shastri, Time-relaxed broadcasting in communication networks, Discrete Applied mathematics 83 (1998) 263–278] conjectured that B1(22)=24B1(22)=24 and B2(n)=n+1B2(n)=n+1 for 25≤n≤2925≤n≤29. In this paper, we show that B1(22)=24B1(22)=24, B2(n)=nB2(n)=n for 25≤n≤2825≤n≤28 and 37≤n≤4437≤n≤44, B2(n)≤n+1B2(n)≤n+1 for 45≤n≤4945≤n≤49, B2(n)≤n+4B2(n)≤n+4 for 50≤n≤5650≤n≤56, and B3(n)=nB3(n)=n for 55≤n≤6455≤n≤64.