Key points are not available for this paper at this time.
Abstract Chung et al. constructed an induced subgraph of the hypercube with vertices and with maximum degree smaller than . Subsequently, Huang proved the Sensitivity Conjecture by demonstrating that the maximum degree of such an induced subgraph of hypercube is at least , and posed the question: Given a graph , let be the minimum of the maximum degree of an induced subgraph of on vertices, what can we say about ? In this paper, we investigate this question for Cartesian product of paths , denoted by . We determine the exact values of when by showing that for and , and give a nontrivial lower bound of when by showing that . In particular, when , we have , which is Huang's result. The lower bounds of and are given by using the spectral method provided by Huang.
Zeng et al. (Thu,) studied this question.