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

If \(G\) is an \(m\)-connected graph, \(S\) is a subset of its vertex set \(V(G)\), \(y\) is a vertex of \(V(G)- S\) and \(d\) and \(m\) are positive integers, then \(S\) is said to \((d,m)\)-dominate \(y\), if there exist \(m\) internally disjoint paths of length \(d\) which connect \(y\) with vertices of \(S\). If \(S= V(G)\) or \(S\) \((d,m)\)-dominates all vertices of \(V(G)-S\), then \(S\) is called a \((d,m)\)-dominating set in \(G\). The minimum number of vertices of a \((d,m)\)-dominating set in \(G\) is the \((d,m)\)-dominating number \(s_{d,m}(G)\) of \(G\). The binary directed de Bruijn graph \(\text{B}(n)\) is the directed graph with \(2^n\) vertices labeled by binary strings over \(\{0,1\}\) of length \(n\). Arcs of \(\text{B}(n)\) go from vertices \(x_1x_2\dots x_n\) to \(x_2x_3\dots x_n0\) and \(x_2x_3\dots x_n1\). By omitting the orientation and deleting thus obtained loops and multiple edges the undirected binary de Bruijn graph \(\text{UB}(n)\) is obtained. The main results are the following: (1) For \(n\geq 4\), there is a vertex \(x= x_1\overline x_1\overline x_1\dots\overline x_1 x_1\) (where \(x_1= 1\) or \(x_1=0\)) in \(\text{UB}(n)\) such that for any other vertex \(t\) there exist two internally disjoint paths of length at most \(n-1\) between \(x\) and \(t\), i.e. \(s_{n-1,2}(\text{UB}(n))= 1\). (2) For \(n\geq 5\), let \(S= \{100\dots 01\), \(011\dots 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 \(\text{UB}(n)\), i.e. \(s_{n-2,2}(\text{UB}(n))\leq 2\).