E-resources
Peer reviewed
Open access
-
Tandya, Vincent
Journal of graph theory, October 2022, 2022-10-00, 20221001, Volume: 101, Issue: 2Journal Article
For every graph G $G$, let α ( G ) $\alpha (G)$ denote its independence number. What is the minimum of the maximum degree of an induced subgraph of G $G$ with α ( G ) + 1 $\alpha (G)+1$ vertices? We study this question for the n $n$‐dimensional Hamming graph over an alphabet of size k $k$. In this paper, we give a construction to prove that the answer is 1 for all n $n$ and k $k$ with k ≥ 3 $k\ge 3$. This is an improvement over an earlier work showing that the answer is at most ⌈ n ⌉ $\lceil \sqrt{n}\rceil $.
