An induced subgraph of the Hamming graph with maximum degree 1
An induced subgraph of the Hamming graph with maximum degree 1
复制标题
最大度为 1 的汉明图的诱导子图
DOI：
10.1002/jgt.22828
复制
发表时间：
2021
影响因子：
0.9
通讯作者：
Vincent Tandya
中科院分区：
文献类型：
--
作者：
Vincent Tandya
对任意图G $G$，设α（G）$\alpha（G）$表示其独立数. G $G$中顶点数为α（G）+1 $\alpha（G）+1 $的导出子图的最大度的最小值是多少？我们研究了k $k$上的n $n$-维Hamming图的这个问题。本文给出了一个构造，证明了对所有n $n$和k $k$，且k ≥ 3 $k\ge 3$，答案为1。这是对早期工作的改进，该工作表明答案最多为{n}\lceil \sqrt{n}\rceil $。
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 $ .