A new method for constructing minimal broadcast networks (Q5905613)

Let \(G\) be a connected graph. The broadcast time of a node \(v\) in \(G\), denoted by \(t(v)\), is defined to be the least number of time units required to complete broadcast from \(v\). The broadcast time of \(G\), denoted by \(t(G)\), is the minimum \(t(v)\) over all \(v\) in \(G\). Obviously \(t(G)\geq\lceil\log n\rceil\). For each \(n\) let \(\text{mbn}(n)\) be the set of all graphs of order \(n\) such that their broadcast time equals \(\lceil\log n\rceil\), and \(b(n)\) the least number of edges of graphs over \(\text{mbn}(n)\). A graph is called minimum broadcast graph if it is in \(\text{mbn}(n)\) and the number of its edges equals \(b(n)\). This paper presents a method for constructing graphs in \(\text{mbn}(n)\) and gives upper bounds of \(b(n)\) for \(19\leq n\leq 30\).