On Induced Subgraph of Cartesian Product of Paths

arXiv2306.04110MaRDI QIDQ6439461FDOQ6439461

Authors: Jiasheng Zeng, Xinmin Hou 

Publication date: 6 June 2023

Abstract: Chung, F"uredi, 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 $lceilsqrtnceil$. Subsequently, Huang (Annals of Mathematics, 2019) proved the Sensitivity Conjecture by demonstrating that the maximum degree of such an induced subgraph of hypercube $Q^n$ is at least $lceilsqrtnceil$, and posed the question: Given a graph $G$, let $f(G)$ be the minimum of the maximum degree of an induced subgraph of $G$ on $alpha(G)+1$ vertices, what can we say about $f(G)$? In this paper, we investigate this question for Cartesian product of paths $P_m$, denoted by $P_m^k$. We determine the exact values of $f(P_m^k)$ when $m=2n+1$ by showing that $f(P_{2n+1}^k)=1$ for $ngeq2$ and $f(P_3^k)=2$, and give a nontrivial lower bound of $f(P_m^k)$ when $m=2n$ by showing that $$. In particular, when $n=1$, we have $f(Q^k)=f(P_2^k)gesqrtk$, which is Huang's result. The lower bounds of $f(P_3^k)$ and $f(P_{2n}^k)$ are given by using the spectral method provided by Huang.

This page was built for publication: On Induced Subgraph of Cartesian Product of Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439461)