In this paper, we show that: (i) For n-dimensional undirected binary de Bruijn graphs, UB(n), n>4, there is a vertex x=x1x1x1 x1x1 (x1=1 or 0) such that for any other vertex t there exist at least two internally disjoint paths of length at most n 1 between x and t in UB(n), i.e., the (n 1;2)-dominating number ofUB(n) is equal to one. (ii) Forn>5, letS=f100 01;011 10g. For any other vertex t there exist at least two internally disjoint paths of length at most n 2 between t and S in UB(n), i.e., the (n 2;2)-dominating number of UB(n) is no more than 2. ? 2000 Elsevier Science B.V. All rights reserved.
['C. J. Lu', 'Juming Xu', 'Kemin Zhang']
On ( d , 2)-dominating numbers of binary undirected de Bruijn graphs