Aaron Potechin ; Hing Yin Tsang - On induced subgraphs of $H(n,3)$ with maximum degree $1$

dmtcs:15440 - Discrete Mathematics & Theoretical Computer Science, February 6, 2026, vol. 28:2 - https://doi.org/10.46298/dmtcs.15440
On induced subgraphs of $H(n,3)$ with maximum degree $1$Article

Authors: Aaron Potechin ; Hing Yin Tsang

    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| \leq 3^{n-1}+1$. Moreover, all such $U$ with size $3^{n-1}+1$ are isomorphic to each other.
    2. For $n \geq 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 ϕ$ for all $x \in \mathbb{Z}_3^n$ then $|U| \leq 3^{n-1} + 81$.

    41 pages. This is the journal version of our paper


    Volume: vol. 28:2
    Section: Graph Theory
    Published on: February 6, 2026
    Accepted on: December 28, 2025
    Submitted on: March 31, 2025
    Keywords: Combinatorics, G.2.2

    Consultation statistics

    This page has been seen 64 times.
    This article's PDF has been downloaded 37 times.