On paths and cycles dominating hypercubes

DOI10.1016/S0012-365X(02)00524-1MaRDI QIDQ1868842zbMATH OpenOpenAlexFDO

Authors Tomáš Dvořák, Michel Mollard, Ivan Havel

Publication date 28 April 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00524-1

zbMATH Keywords

dominating cycledominating pathdominationhypercube

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

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.

Recommendations

• Short dominating paths and cycles in the binary hypercube
• On path bipancyclicity of hypercubes
• Cycles and paths embedded in varietal hypercubes
• Paths and cycles of hypergraphs
• Path bipancyclicity of hypercubes
• A note on path bipancyclicity of hypercubes
• scientific article; zbMATH DE number 57430
• Edge decompositions of hypercubes by paths and by cycles
• Spanning paths in hypercubes
• On crossing numbers of hypercubes and cube connected cycles

Cited in

(12)

• Paths and cycles of hypergraphs
• Edge decompositions of hypercubes by paths and by cycles
• Independent domination in hypercubes
• Spanning multi-paths in hypercubes
• The domination number of exchanged hypercubes
• scientific article; zbMATH DE number 617558 (Why is no real title available?)
• scientific article; zbMATH DE number 871180 (Why is no real title available?)
• scientific article; zbMATH DE number 1444489 (Why is no real title available?)
• Spanning trees and domination in hypercubes
• Short dominating paths and cycles in the binary hypercube
• Improved lower bounds on the domination number of hypercubes and binary codes with covering radius one
• On crossing numbers of hypercubes and cube connected cycles

This page was built for publication: On paths and cycles dominating hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1868842)