On paths and cycles dominating hypercubes (Q1868842): Difference between revisions

Let \(\text{c}_n\), \(\text{p}_n\) and \(\text{cyc}_n\) denote the minimum number of vertices in a dominating set, a dominating path and a dominating cylce of the \(n\)-dimensional hypercube, respectively. The authors prove that \(\text{cyc}_n \leq 2^{m-p}(2^k+2)\) for \(p\geq 2\), \(m=2^p-1\), \(1\leq k\leq 2^p\) and \(n=m+k\), \(\text{c}_n\geq 2\lceil\frac{2^{n-1}-2}{n-2}\rceil\) for \(n\geq 3\) and \(\text{cyc}_n \geq 2\lceil\frac{2^{n-1}}{n-2}\rceil\) for \(n\geq 4\). Furthermore, they prove so-called interpolation results for \(\text{p}_n\) and \(\text{cyc}_n\): For every \(n\geq 2\) and every integer (even integer) \(i\) with \(\text{p}_n\leq i\leq 2^n\) (\(\text{cyc}_n\leq i\leq 2^n\)) there is a dominating path (cycle) containing \(i\) vertices.