Affiliation: | a Sanjiang University, Nanjing 210012, China b Department of Mathematics, Hong Kong Baptist University, Kowloon, Hong Kong c Department of Applied Mathematics, Southeast University, Nanjing 210096, China d State Key Laboratory for Novel Software Technology at Nanjing University, Department of Mathematics, Nanjing University, Nanjing 210093, China |
Abstract: | 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≥0, let Bt(n) be the number of edges in the sparsest possible graph on n vertices in which broadcasting can be accomplished in ⌈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)=24 and B2(n)=n+1 for 25≤n≤29. In this paper, we show that B1(22)=24, B2(n)=n for 25≤n≤28 and 37≤n≤44, B2(n)≤n+1 for 45≤n≤49, B2(n)≤n+4 for 50≤n≤56, and B3(n)=n for 55≤n≤64. |