On open and edge open packings of hypercubes
Motivated by questions of Brešar, Samadi and Yero (Discrete Math. 346 (2023), 113348) on injective coloring, we identify the open packing number of the n -dimensional hypercube Q n exactly with standard coding-theoretic quantities by showing that ρ o ( Q n ) = 2 A 2 ( n − 1 , 3 ) = 2 A 2 ( n , 4 ) , where A 2 ( n , d ) is the maximum size of a binary code of length n and minimum distance at least d . This translates known results from coding theory into values of ρ o ( Q n ) . In particular, this gives ρ o ( Q 9 ) = 40 , improving the previously known bounds. We further prove that Q n is perfect injectively colorable if and only if A 2 ( n − 1 , 3 ) is a power of two, equivalently if and only if A 2 ( n − 1 , 3 ) = 2 n − 1 − ⌈ log 2 n ⌉ . For the edge analogue studied by Brešar, Dravec, Hedžet and Samadi (Discrete Math. 348 (2025), 114458), we give an explicit syndrome construction inspired by extended Hamming codes. It recovers the sharp value ρ e o ( Q n ) = 2 n − 1 when n is a power of two, and gives lower bounds that attain a 1 − o ( 1 ) fraction of the general upper bound 2 n − 1 in all dimensions. In particular, it gives ρ e o ( Q 9 ) ≥ 224 , improving the bound ρ e o ( Q 9 ) ≥ 180 obtained from the earlier general construction. We also show that the upper bound 2 n − 1 for ρ e o ( Q n ) is attained precisely in power-of-two dimensions, and sharpen it to 2 n − 1 − 2 when n ≥ 4 is not a power of two.
Authors
- Juho Lauri (ORCID: https://orcid.org/0000-0002-6781-6106)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2026-09-11
- DOI
- https://doi.org/10.1016/j.disc.2026.115427
- Primary Topic
- graph theory and CDMA systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00