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

In this paper, we show that: (i) For n-dimensional undirected binary de Bruijn graphs, UB(n), n≥4, there is a vertex x=x₁x̄₁x̄₁x̄₁x ₁ (x₁=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 of UB(n) is equal to one. (ii) For n≥5, let S={10001,01110}. 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.