An induced subgraph of the Hamming graph with maximum degree 1

2021/07/29 by Tandya, Vincent · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2107.13816

Abstract

For every graph G, let α(G) denote its independence number. What is the minimum of the maximum degree of an induced subgraph of G with α(G)+1 vertices? We study this question for the n-dimensional Hamming graph over an alphabet of size k. In this paper, we give a construction to prove that the answer is 1 for all n and k with k ≥ 3. This is an improvement over an earlier work showing that the answer is at most \lceil √(n) \rceil.

Cited by

• Graph Sensitivity under Join and Decomposition
• Sensitivity and Hamming graphs

Related

• On Induced Subgraphs of the Hamming Graph
• On induced subgraphs of H(n,3) with maximum degree 1
• Equating two maximum degrees
• New approach to the k-independence number of a graph
• Induced subgraphs with many repeated degrees