The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007192 Number of edges in minimal broadcast graph with n nodes.
(Formerly M0508)
0, 1, 2, 4, 5, 6, 8, 12, 10, 12, 13, 15, 18, 21, 24, 32, 22, 23, 25, 26, 28, 31 (list; graph; refs; listen; history; text; internal format)



Sources for values a(n), from A. L. Liestman:


1-16: Farley, Hedetniemi, Mitchell and Proskurowski

17: Hedetniemi and Mitchell "Census"

18-19: Xiao and Wang (reported in Bermond, Hell, Liestman and Peters)

20-23: Maheo and Sacle

24-25: Bermond, Hell, Liestman and Peters

26-29: Sacle (in Discrete Applied Math. 150, pp. 359-360, 1996); the value for n=26 was found independently by Chen (unpublished) and by Zhou and Zhang

30-31: Bermond, Hell, Liestman and Peters

32: Farley, Hedetniemi, Mitchell and Proskurowski

33-34: Weng and Ventura (in Telecomm. Systems 3, pp. 259-293, 1995)

35-36: Bermond, Fraigniaud and Peters

37-40: Bermond, Hell, Liestman and Peters

41-46: Bermond, Fraigniaud and Peters

47-48: Bermond, Fraigniaud and Peters

See Bermond, Fraigniaud and Peters for details of other references


Bermond, Jean-Claude; Fraigniaud, Pierre; and Peters, Joseph G., Antepenultimate broadcasting Networks 26 (1995), 125-137.

Bermond, Jean-Claude; Hell, Pavol; Liestman, Arthur L.; Peters, Joseph G. Broadcasting in bounded degree graphs. SIAM J. Discrete Math. 5 (1992), no. 1, 10-24.

Farley, Arthur; Hedetniemi, Stephen; Mitchell, Sandra; Proskurowski, Andrzej Minimum broadcast graphs. Discrete Math. 25 (1979), 189-193.

S. M. Hedetniemi, S. T. Hedetniemi and A. L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks, 18 (1988), 319-349.

A. L. Liestman and J. G. Peters, Broadcast networks of bounded degree, SIAM J. Discrete Math., 1 (1988), 531-540.

Maheo, M. and Sacle, J.-F., Some minimum broadcast graphs, in Proceedings International Workshop on Broadcasting and Gossiping 1990 (Sechelt, BC). Discrete Appl. Math. 53 (1994), 275-285.

Mitchell, Sandra and Hedetniemi, Stephen, A census of minimum broadcast graphs. J. Combin. Inform. System Sci. 5 (1980), no. 2, 141-151.

Sacle, J.-F., Lower bounds for the size in four families of minimum broadcast graphs. Selected papers in honour of Paul Erdős on the occasion of his 80th birthday (Keszthely, 1993). Discrete Math. 150 (1996), 359-369.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J.-G. Zhou and K.-M. Zhang, A minimum broadcast graph on 26 vertices, Appl. Math. Lett. 14 (2001), 1023-1026.


Table of n, a(n) for n=1..22.


a(2^k) = k*2^(k-1), a(2^k-2) = (k-1)*(2^(k-1)-1).


Sequence in context: A099247 A192583 A240064 * A081354 A119792 A085834

Adjacent sequences:  A007189 A007190 A007191 * A007193 A007194 A007195




Simon Plouffe


Entry revised (and corrected and extended) by N. J. A. Sloane Mar 20 2005, using information kindly supplied by Art Liestman.

Upper bounds for the next three entries a(23), a(24), a(25) are 34, 36, 40.



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 15 00:08 EDT 2022. Contains 356122 sequences. (Running on oeis4.)