On induced subgraphs of $H(n,3)$ with maximum degree $1$

Abstract

In this paper, we consider induced subgraphs of the Hamming graph $H(n,3)$. We show that if $U\subseteq {\mathbb{Z}}_3^n$ and $U$ induces a subgraph of $H(n,3)$ with maximum degree at most $1$ then 1. If $U$ is disjoint from a maximum size independent set of $H(n,3)$ then $|U|\le 3^{n-1}+1$. Moreover, all such $U$ with size $3^{n-1}+1$ are isomorphic to each other. 2. For $n\ge 6$, there exists such a $U$ with size $|U|=3^{n-1}+18$ and this is optimal for $n=6$. 3. If $U\cap \{x,x+e_1,x+2e_1\}\ne \varphi$ for all $x\in {\mathbb{Z}}_3^n$ then $|U|\le 3^{n-1}+81$.

41 pages. This is the journal version of our paper