----------------------------------------------
 |          TECHNICAL REPORT ECE-95-5           |
 |                 August 1995                  |
 | Dept. of Electrical and Computer Engineering |
 |           University of Victoria             |
  ----------------------------------------------


TITLE:   On Broadcasting Time

AUTHORS: Vassilios V. Dimakopoulos and Nikitas J. Dimopoulos

NOTE:    Submitted for publication

ABSTRACT

Broadcasting is an information dissemination problem in which a
particular node in a network must transmit an item of information
to all the other nodes in the network. In this work we present 
new lower bounds for the time needed to complete this process in 
arbitrary graphs. In particular we generalize a result of 
P. Friagniaud and E. Lazard [Discrete Applied Mathematics, 
53 (1994) 79--133] which states that if in a graph there are at 
least two vertices in distance equal to the diameter from the 
originator, then broadcasting requires time at least equal to 
the diameter plus one.