Improved lower bounds on the domination number of hypercubes and binary codes with covering radius one

DOI10.1016/J.DISC.2023.113752MaRDI QIDQ6184529zbMATH OpenOpenAlexFDO

Authors Ying-Sian Wu, J. Y. Chen

Publication date 25 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.16901

zbMATH Keywords

domination numberdominating sethypercubescovering codescovering radiusbinary codes

Mathematics Subject Classification ID

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 operations (line graphs, products, etc.) (05C76) Bounds on codes (94B65) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: A dominating set on an $n$-dimensional hypercube is equivalent to a binary covering code of length $n$ and covering radius 1. It is still an open problem to determine the domination number $gamma(Q_n)$ for $ngeq9$ and $ne{2}^k,2^k-1$ ($kinmathbbN$). When $n$ is a multiple of 6, the best known lower bound is $gamma(Q_n)geqfrac{2}^{n}n$, given by Van Wee (1988). In this article, we present a new method using congruence properties due to Laurent Habsieger (1997) and obtained an improved lower bound $gamma(Q_n)geqfrac(n-2)2^n{n}^2-2n-2$ when $n$ is a multiple of 6.

Recommendations

• On independent and \((d, n)\)-domination numbers of hypercubes
• scientific article; zbMATH DE number 2234856
• On paths and cycles dominating hypercubes
• scientific article; zbMATH DE number 1444489
• The domination number of exchanged hypercubes

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 3054152 (Why is no real title available?)
• A Combinatorial Problem in Matching
• A remark on Haas' method
• An updated table of binary/ternary mixed covering codes
• Constructing covering codes with given automorphisms
• Covering problems for dichotomized matchings
• Further results on the covering radius of codes
• Improved sphere bounds on the covering radius of codes
• Lower Bounds for Binary Codes of Covering Radius One
• New binary covering codes obtained by simulated annealing
• New lower bounds for binary covering codes
• New lower bounds for covering codes
• New upper bounds for binary covering codes
• On the size of optimal binary codes of length 9 and covering radius 1
• Several new lower bounds on the size of codes with covering radius one
• Types of superregular matrices and the number of n‐arcs and complete n‐arcs in PG (r, q)

This page was built for publication: Improved lower bounds on the domination number of hypercubes and binary codes with covering radius one

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