|
%I M0508 #13 Jul 21 2015 11:31:47
%S 0,1,2,4,5,6,8,12,10,12,13,15,18,21,24,32,22,23,25,26,28,31
%N Number of edges in minimal broadcast graph with n nodes.
%C Sources for values a(n), from A. L. Liestman:
%C n.....Source
%C 1-16: Farley, Hedetniemi, Mitchell and Proskurowski
%C 17: Hedetniemi and Mitchell "Census"
%C 18-19: Xiao and Wang (reported in Bermond, Hell, Liestman and Peters)
%C 20-23: Maheo and Sacle
%C 24-25: Bermond, Hell, Liestman and Peters
%C 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
%C 30-31: Bermond, Hell, Liestman and Peters
%C 32: Farley, Hedetniemi, Mitchell and Proskurowski
%C 33-34: Weng and Ventura (in Telecomm. Systems 3, pp. 259-293, 1995)
%C 35-36: Bermond, Fraigniaud and Peters
%C 37-40: Bermond, Hell, Liestman and Peters
%C 41-46: Bermond, Fraigniaud and Peters
%C 47-48: Bermond, Fraigniaud and Peters
%C See Bermond, Fraigniaud and Peters for details of other references
%D Bermond, Jean-Claude; Fraigniaud, Pierre; and Peters, Joseph G., Antepenultimate broadcasting Networks 26 (1995), 125-137.
%D 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.
%D Farley, Arthur; Hedetniemi, Stephen; Mitchell, Sandra; Proskurowski, Andrzej Minimum broadcast graphs. Discrete Math. 25 (1979), 189-193.
%D S. M. Hedetniemi, S. T. Hedetniemi and A. L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks, 18 (1988), 319-349.
%D A. L. Liestman and J. G. Peters, Broadcast networks of bounded degree, SIAM J. Discrete Math., 1 (1988), 531-540.
%D 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.
%D Mitchell, Sandra and Hedetniemi, Stephen, A census of minimum broadcast graphs. J. Combin. Inform. System Sci. 5 (1980), no. 2, 141-151.
%D 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D J.-G. Zhou and K.-M. Zhang, A minimum broadcast graph on 26 vertices, Appl. Math. Lett. 14 (2001), 1023-1026.
%F a(2^k) = k*2^(k-1), a(2^k-2) = (k-1)*(2^(k-1)-1).
%K nonn,more,nice
%O 1,3
%A _Simon Plouffe_
%E Entry revised (and corrected and extended) by _N. J. A. Sloane_ Mar 20 2005, using information kindly supplied by Art Liestman.
%E Upper bounds for the next three entries a(23), a(24), a(25) are 34, 36, 40.
|
