Broadcasting and spanning trees in de Bruijn and Kautz networks

AbstractWe prove that, for any p≤d, there exists a spanning directed p-ary tree of depth at most D⌈logpd⌉; in a de Bruijn digraph B(d,D) or in a Kautz digraph K(d,D) of degree d and diameter D. This result gives directly an upper bound of pD⌈logpd⌉ on the broadcast time of these digraphs, which improves the previously known bounds for d≥15. In the case of de Bruijn digraphs, an upper bound on the broadcast time of B(pq,D) in terms of the broadcast times of B(p,D) and B(q,D) is established. This is used to improve the upper bounds on the broadcast time of B(d,D). We obtain several results which are refinements of the following general statements: 1.(i) for any D⩾2, d⩾2, if 2kl <d⩽2k, b(B(d, D))⩽(54k+3)D.2.(ii) for any k⩾3, if 2k 1