Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.15004 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915850721689600 |
|---|---|
| author | Potechin, Aaron Tsang, Hing Yin |
| author_facet | Potechin, Aaron Tsang, Hing Yin |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_15004 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On induced subgraphs of $H(n,3)$ with maximum degree $1$ Potechin, Aaron Tsang, Hing Yin Combinatorics G.2.2 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$. |
| title | On induced subgraphs of $H(n,3)$ with maximum degree $1$ |
| topic | Combinatorics G.2.2 |
| url | https://arxiv.org/abs/2405.15004 |