Lower bounds for the size in four families of minimum broadcast graphs (Q1916125)

Given a graph \(G_n\) of \(n\) vertices, the broadcasting problem consists of passing some information, starting from a single informed vertex \(x\), to all other vertices, where in each step each informed vertex can pass the information on to at most one of its neighbours. A simple bound for the number of steps needed is \(\lceil\log_2(n)\rceil\), since in each step the number of informed vertices at most doubles. A broadcast graph is a graph \(G_n\) where for each starting vertex there exists a strategy that reaches all other vertices in this minimum time. The author studies the minimum number of edges \(B(n)\) of a broadcast graph on \(n\) vertices. This number is known for \(n\) of the form \(2^k-2\) where \(k\geq 4\). The author proves lower bounds for \(n\) of the forms \(2^k-3\), \(2^k-4\), \(2^k-5\), \(2^k-6\), and determines some exact values which give the right values for \(k=5, 6\).