New Upper Bounds on the Minimal Domination Numbers of High-Dimensional Hypercubes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912040419852288 |
|---|---|
| author | DeVivo, Zachary Hladky, Robert K. |
| author_facet | DeVivo, Zachary Hladky, Robert K. |
| contents | We briefly review known results on upper bounds for the minimal domination number $γ_n$ of a hypercube of dimension $n$, then present a new method for constructing dominating sets.
Write $n =2^{\hat{n}}-1 +{\check{n}}$ with $0\leq {\check{n}}<2^{\hat{n}}$. Our construction applies to all $n$ lying within the expanding wedge $θ({\hat{n}}) \leq {\check{n}} < 2^{\hat{n}}$, where $θ$ is a specific, easily computable function with the asymptotic property $θ(a) \sim 2^{a/2}$. For all $n$ within the smaller wedge $θ({\hat{n}}) \leq {\check{n}} < 2^{\hat{n}-2}$, the resulting upper bound on $γ_n$ betters those previously known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14621 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New Upper Bounds on the Minimal Domination Numbers of High-Dimensional Hypercubes DeVivo, Zachary Hladky, Robert K. Combinatorics 05C69, 94B05 We briefly review known results on upper bounds for the minimal domination number $γ_n$ of a hypercube of dimension $n$, then present a new method for constructing dominating sets. Write $n =2^{\hat{n}}-1 +{\check{n}}$ with $0\leq {\check{n}}<2^{\hat{n}}$. Our construction applies to all $n$ lying within the expanding wedge $θ({\hat{n}}) \leq {\check{n}} < 2^{\hat{n}}$, where $θ$ is a specific, easily computable function with the asymptotic property $θ(a) \sim 2^{a/2}$. For all $n$ within the smaller wedge $θ({\hat{n}}) \leq {\check{n}} < 2^{\hat{n}-2}$, the resulting upper bound on $γ_n$ betters those previously known. |
| title | New Upper Bounds on the Minimal Domination Numbers of High-Dimensional Hypercubes |
| topic | Combinatorics 05C69, 94B05 |
| url | https://arxiv.org/abs/2409.14621 |