EUVIMEDEUVIMED entdecken
Crossref

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

Aaron Potechin, Hing Yin Tsang

Discrete Mathematics & Theoretical Computer Science · 06.02.2026 · vol. 28:2 (Graph Theory)

DOI: 10.46298/dmtcs.15440 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 06.02.2026. Verfasst von Aaron Potechin und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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

Zitieren

APA

Potechin, A., & Tsang, H. Y. (2026). On induced subgraphs of $H(n,3)$ with maximum degree $1$. Discrete Mathematics & Theoretical Computer Science, vol. 28:2(Graph Theory). https://doi.org/10.46298/dmtcs.15440

Vancouver

Potechin A, Tsang HY. On induced subgraphs of $H(n,3)$ with maximum degree $1$. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:2(Graph Theory). doi:10.46298/dmtcs.15440

BibTeX
@article{Potechin2026,
  author = {Potechin, Aaron and Tsang, Hing Yin},
  title = {On induced subgraphs of $H(n,3)$ with maximum degree $1$},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2026},
  volume = {vol. 28:2},
  number = {Graph Theory},
  doi = {10.46298/dmtcs.15440}
}
Kostenlos starten →