Efficient construction of broadcast graphs

A broadcast graph is a connected graph, G=(V,E)G=(V,E), |V|=n|V|=n, in which each vertex can complete broadcasting of one message within at most t=⌈logn⌉t=⌈logn⌉ time units. A minimum broadcast graph on nn vertices is a broadcast graph with the minimum number of edges over all broadcast graphs on nn vertices. The cardinality of the edge set of such a graph is denoted by B(n)B(n). In this paper we construct a new broadcast graph with B(n)≤(k+1)N−(t−k2+2)2k+t−k+2, for n=N=(2k−1)2t+1−kn=N=(2k−1)2t+1−k and B(n)≤(k+1−p)n−(t−k2+p+2)2k+t−k−(p−2)2p, for 2t0x>0 and p=0p=0 if x=0x=0.The new bound is an improvement upon the bounds appeared in Bermond et al. (1995), Bermond et al. (1997), Fertin and Raspaud (2004) and Harutyunyan and Leistman (1999) and the recent bound presented by Harutyunyan and Liestman (2012) for odd values of nn.