What question did this study set out to answer?

The paper aims to explore the properties of induced subgraphs in the Hamming graph H(n,3) with a maximum degree of 1.

February 9, 2026Discrete Mathematics & Theoretical Computer Science0 citationsOpen Access

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

APAaron PotechinUniversity of Chicago HTHing Yin TsangChinese University of Hong Kong

Key Points

The paper aims to explore the properties of induced subgraphs in the Hamming graph H(n,3) with a maximum degree of 1.
Considered induced subgraphs of the Hamming graph H(n,3)
Analyzed size constraints based on independent set properties
Evaluated specific conditions affecting the size of subsets U
If U is disjoint from a maximum size independent set, then |U| ≤ 3^(n-1) + 1
For n ≥ 6, there exists a U with |U| = 3^(n-1) + 18, which is optimal for n = 6
If U intersects with certain vectors, then |U| ≤ 3^(n-1) + 81

Abstract

In this paper, we consider induced subgraphs of the Hamming graph H (n, 3). We show that if U Z₃ⁿ 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| 3^n-1+1. Moreover, all such U with size 3^n-1+1 are isomorphic to each other. 2. For n 6, there exists such a U with size |U| = 3^n-1+18 and this is optimal for n = 6. 3. If U \x, x+e₁, x+2e₁\ ϕ for all x Z₃ⁿ then |U| 3^n-1 + 81. 41 pages. This is the journal version of our paper

Demander à l'IA

Bookmark

View Full Paper