Induced subgraphs of product graphs and a generalization of Huang's theorem

Abstract

Recently, Huang showed that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional hypercube has maximum degree at least $\sqrt{n}$ in [Annals of Mathematics, 190 (2019), 949--955]. In this paper, we discuss the induced subgraphs of Cartesian product graphs and semi-strong product graphs to generalize Huang's result. Let ${\Gamma }_1$ be a connected signed bipartite graph of order $n$ and ${\Gamma }_2$ be a connected signed graph of order $m$. By defining two kinds of signed product of ${\Gamma }_1$ and ${\Gamma }_2$, denoted by ${\Gamma }_1\tilde{\square }{\Gamma }_2$ and ${\Gamma }_1\tilde{\bowtie }{\Gamma }_2$, we show that if ${\Gamma }_1$ and ${\Gamma }_2$ have exactly two distinct adjacency eigenvalues $\pm {\theta }_1$ and $\pm {\theta }_2$ respectively, then every $(\frac{1}{2}mn+1)$-vertex induced subgraph of ${\Gamma }_1\tilde{\square }{\Gamma }_2$ (resp. ${\Gamma }_1\tilde{\bowtie }{\Gamma }_2$) has maximum degree at least $\sqrt{{\theta }_1^2+{\theta }_2^2}$ (resp. $\sqrt{({\theta }_1^2+1){\theta }_2^2}$). Moreover, we discuss the eigenvalues of ${\Gamma }_1\tilde{\square }{\Gamma }_2$ and ${\Gamma }_1\tilde{\bowtie }{\Gamma }_2$ and obtain a sufficient and necessary condition such that the spectrum of ${\Gamma }_1\tilde{\square }{\Gamma }_2$ and ${\Gamma }_1\tilde{\bowtie }{\Gamma }_2$ are symmetric, from which we obtain more general results on maximum degree of the induced subgraphs.

18 pages, 2 figures, Related to induced graphs of the hypercube

References in corpus (1)

• Open problems in the spectral theory of signed graphs