New Upper Bounds on the Minimal Domination Numbers of High-Dimensional Hypercubes

2024/09/22 by Zachary DeVivo, DeVivo, Zachary, Robert K. Hladky +1
Computer Science · Engineering · #05C69 #94B05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Satellite Communication Systems

paper · pdf · doi:10.48550/arxiv.2409.14621

openalex publication_date 2024/09/22 · openalex created_date 2024/10/26 · openalex updated_date 2026/07/28

Abstract

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^n-1 +\checkn with 0≤ \checkn<2^n. Our construction applies to all n lying within the expanding wedge θ(n) ≤ \checkn < 2^n, where θ is a specific, easily computable function with the asymptotic property θ(a) ∼ 2^a/2. For all n within the smaller wedge θ(n) ≤ \checkn < 2^n-2, the resulting upper bound on γ_n betters those previously known.

Related

• Improved Upper Bound on Independent Domination Number for Hypercubes
• (Total) Domination in Prisms
• Spanning Trees and Domination in Hypercubes
• The domination number of the graph defined by two levels of the n-cube, II
• Multipacking in Hypercubes