Short dominating paths and cycles in the binary hypercube (Q5939208)

It is well known that the \(n\)-cube can be defined as the graph whose vertex set consists of all \(2^n\) \(n\)-tuples of \(0\)'s and \(1\)'s where two \(n\)-tuples are adjacent if and only if they differ in exactly one position. The Hamming distance between two \(n\)-tuples is equal to the number of positions in which they differ. A sequence of \(n\)-tuples is said to be a cube dominating path if the Hamming distance between two consecutive \(n\)-tuples is one and if every \(n\)-tuple is within Hamming distance one from at least one of the \(n\)-tuples in the sequence. If the first and last \(n\)-tuple in this sequence are the same, then the sequence is said to be a cube dominating cycle. The authors obtain bounds on the shortest such sequences and show that they contain asymptotically \(2^n(1 + o(1))/n\) elements.