Premium
An induced subgraph of the Hamming graph with maximum degree 1
Author(s) -
Tandya Vincent
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22828
Subject(s) - combinatorics , mathematics , alphabet , hamming graph , factor critical graph , degree (music) , graph , induced subgraph , induced subgraph isomorphism problem , discrete mathematics , independence number , line graph , hamming code , graph power , voltage graph , algorithm , vertex (graph theory) , philosophy , linguistics , decoding methods , physics , acoustics , block code
For every graphG$G$ , letα ( G )$\alpha (G)$ denote its independence number. What is the minimum of the maximum degree of an induced subgraph ofG$G$ withα ( G ) + 1$\alpha (G)+1$ vertices? We study this question for then$n$ ‐dimensional Hamming graph over an alphabet of sizek$k$ . In this paper, we give a construction to prove that the answer is 1 for alln$n$ andk$k$ withk ≥ 3$k\ge 3$ . This is an improvement over an earlier work showing that the answer is at most⌈ n ⌉$\lceil \sqrt{n}\rceil $ .