Premium
On induced subgraphs of the Hamming graph
Author(s) -
Dong Dingding
Publication year - 2021
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.22640
Subject(s) - combinatorics , mathematics , conjecture , alphabet , graph , hamming graph , degree (music) , induced subgraph , discrete mathematics , hamming code , vertex (graph theory) , algorithm , decoding methods , block code , philosophy , linguistics , physics , acoustics
In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph G with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of G with α ( G ) + 1 vertices, where α ( G ) denotes the size of the largest independent set in G ? We study this question for H ( n , k ) , the n ‐dimensional Hamming graph over an alphabet of size k . Generalizing a construction by Chung et al. (JCT‐A, 1988), we prove that H ( n , k ) has an induced subgraph with more than α ( H ( n , k ) ) vertices and maximum degree at most ⌈ n ⌉ . Chung et al. proved this statement for k = 2 (the n ‐dimensional cube).