An induced subgraph of the Hamming graph with maximum degree 1

For every graphG$G$ , letα ( G )$\alpha (G)$ denote its independence number. What is the minimum of the maximum degree of an induced subgraph ofG$G$ withα ( G ) + 1$\alpha (G)+1$ vertices? We study this question for then$n$ ‐dimensional Hamming graph over an alphabet of sizek$k$ . In this paper, we give a construction to prove that the answer is 1 for alln$n$ andk$k$ withk ≥ 3$k\ge 3$ . This is an improvement over an earlier work showing that the answer is at most⌈ n ⌉$\lceil \sqrt{n}\rceil $ .