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

Recently, Huang showed that every ( 2 n − 1 + 1 ) ‐vertex induced subgraph of the n ‐dimensional hypercube has maximum degree at least n . In this paper, we discuss the induced subgraphs of Cartesian product graphs and semistrong product graphs to generalize Huang's result. Let Γ 1 be a connected signed bipartite graph of order n and Γ 2 be a connected signed graph of order m . By defining two kinds of signed product of Γ 1 and Γ 2 , denoted by Γ 1 □ ˜ Γ 2 and Γ 1 ⋈ ˜ Γ 2 , we show that if Γ 1 and Γ 2 have exactly two distinct adjacency eigenvalues ± θ 1 and ± θ 2 , respectively, then every ( 1 2 m n + 1 ) ‐vertex induced subgraph of Γ 1 □ ˜ Γ 2 (resp., Γ 1 ⋈ ˜ Γ 2 ) has maximum degree at leastθ 1 2 + θ 2 2(resp.,( θ 1 2 + 1 ) θ 2 2). Moreover, we discuss the eigenvalues of Γ 1 □ ˜ Γ 2 and Γ 1 ⋈ ˜ Γ 2 and obtain a sufficient and necessary condition such that the spectrum of Γ 1 □ ˜ Γ 2 and Γ 1 ⋈ ˜ Γ 2 is symmetric with respect to 0, from which we obtain more general results on maximum degree of the induced subgraphs.