BROADCASTING IN M-DIMENSIONAL GRID GRAPHS WITH A GIVEN NEIGHBORHOOD TEMPLATE

Given a finite nonempty set F of vectors in Z(m), consider the graph G = (V, E) whose vertices are the elements of Z(m) and such that each v ertex v is connected to all vertices v + f for all f is-an-element-of F. Two models of communication have been considered in such graphs: wh ispering (in which a node can only call one neighbor per unit of time) and shouting (in which a node can simultaneously call all of its neig hbors). Let sigma(t) (resp. omega(t)) be the maximum number of nodes t hat can be reached in t steps by a shouting (resp. whispering) broadca st from a single source. This paper deals with the particular case whe re F contains only integer vectors with only one nonzero component. Fo r m = 2, we give the exact form of sigma(t). For m = 2 and when F cont ains only positive vectors we give a concrete upper bound for whisperi ng. We believe that this upper bound can be achieved. Furthermore, whe n F includes the unit vector in each dimension, we describe a whisperi ng broadcast scheme which gives a lower bound of omega(t) in that case . For m greater-than-or-equal-to 3, we prove that for large t both sig ma(t) and omega(t) are of the form [(PI(i=1)i=m(d(i) + c(i))/m!] t(m) + O(t(m-1)) where di (resp. c(i)) is the largest ''positive'' (resp. ' 'negative'') step in the ith dimension, i = 1, ..., m.