On (d,2)-dominating numbers of binary undirected de Bruijn graphs
On \((d,2)\)-dominating numbers of binary undirected de Bruijn graphs
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\).
- scientific article; zbMATH DE number 609926
- On the domination number of $t$-constrained de Bruijn graphs
- On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs
- A new property of binary undirected de Bruijn graphs
- scientific article; zbMATH DE number 1798168
- scientific article; zbMATH DE number 1992420
- On the k-tuple domination of de Bruijn and Kautz digraphs
- The twin domination number in generalized de Bruijn digraphs
- 2-diameter of de Bruijn graphs
- On the twin domination number in generalized de Bruijn and generalized Kautz digraphs
- A new property of binary undirected de Bruijn graphs
- An unoriented variation on de Bruijn sequences
- Matching preclusion and conditional edge-fault Hamiltonicity of binary de Bruijn graphs
- Independence number of de Bruijn graphs
- On the diameter of the generalized undirected de Bruijn graphsUGB(n,m),n2<m≤n3
- scientific article; zbMATH DE number 2075779 (Why is no real title available?)
- Dominance graph of binary words
This page was built for publication: On \((d,2)\)-dominating numbers of binary undirected de Bruijn graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582075)
