Zheng-Jiang Xia

Graph Sensitivity of Cartesian Products with Matched Bridges

For a graph $G$, let $f_t(G)$ denote the minimum of the maximum degree of an induced subgraph with $\alpha(G)+t$ vertices, where $\alpha(G)$ is the independence number, and write $f(G)=f_1(G)$. Huang's theorem gives $f(Q_k)\ge\lceil\sqrt{k}\rceil$ for the $k$-dimensional hypercube $Q_k$. We extend this lower bound to C...