On Induced Subgraph of Cartesian Product of Paths

Jiasheng Zeng, Xinmin Hou

Chung, Füredi, Graham, and Seymour (JCTA, 1988) constructed an induced subgraph of the hypercube $Q^n$ with $\alpha (Q^n)+1$ vertices and with maximum degree smaller than $\lceil \sqrt{n…