Short dominating paths and cycles in the binary hypercube

DOI10.1007/PL00001292MaRDI QIDQ5939208zbMATH OpenFDO

Authors Uri Blass, Iiro Honkala, M. G. Karpovsky, Simon Litsyn

Publication date 14 July 2002

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00001292

zbMATH Keywords

cube dominating cyclecube dominating pathHamming distance

Mathematics Subject Classification ID

Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Bounds on codes (94B65) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Review text

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.

Recommendations

• On paths and cycles dominating hypercubes
• scientific article; zbMATH DE number 434488
• Un nouvel encadrement du nombre de cycle Hamiltoniens du n-cube. (New bounds for the number of Hamiltonian cycles of the n-cube)
• scientific article; zbMATH DE number 790411
• Symmetric routings of the hypercube

Cited in

(5)

• On the identification problems in products of cycles
• On paths and cycles dominating hypercubes
• Dominated error correcting codes with distance two
• scientific article; zbMATH DE number 2014460 (Why is no real title available?)
• Embedding multidimensional grids into optimal hypercubes

This page was built for publication: Short dominating paths and cycles in the binary hypercube

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