On (d, 2)-dominating numbers of binary undirected de Bruijn graphs

In this paper, we show that: (i) For n-dimensional undirected binary de Bru ijn graphs, UB(n), n greater than or equal to 4, there is a vertex x = x(i) (x) over bar(1)(x) over bar(1)...(x) over bar x(1) (x(1) = 1 or 0) such tha t 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)-domi nating number of UB(n) is equal to one. (ii) For n greater than or equal to 5, let S = {100 01...10}. 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. (C) 2000 Elsevier Science B.V. All rights reserved.