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

DOI10.1016/J.DISC.2023.113752arXiv2203.16901OpenAlexW4387796040MaRDI QIDQ6184529FDOQ6184529

Authors: Ying-Sian Wu, J. Y. Chen 

Publication date: 25 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)