On maximal partial Latin hypercubes

Donovan DM, Grannell MJ and Yazıcı EŞ

Designs, Codes and Cryptography


A lower bound is presented for the minimal number of filled cells in a maximal partial Latin hypercube of dimension d and order n. The result generalises and extends previous results for d =2 (Latin squares) and d=3 (Latin cubes). Explicit constructions show that this bound is near-optimal for large n>d. For d>n, a connection with Hamming codes shows that this lower bound gives a related upper bound for the same quantity. The results can be interpreted in terms of independent dominating sets in certain graphs, and in terms of codes that have covering radius 1 and minimum distance at least 2.