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

preprint2020arXivOpen access

Abstract

Recently, Huang showed that every (2n−1+1)(2^{n-1}+1)-vertex induced subgraph of the nn-dimensional hypercube has maximum degree at least n\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 Γ1Γ_1 be a connected signed bipartite graph of order nn and Γ2Γ_2 be a connected signed graph of order mm. By defining two kinds of signed product of Γ1Γ_1 and Γ2Γ_2, denoted by Γ1□~Γ2Γ_1\widetilde{\Box}Γ_2 and Γ1⋈~Γ2Γ_1\widetilde{\bowtie} Γ_2, we show that if Γ1Γ_1 and Γ2Γ_2 have exactly two distinct adjacency eigenvalues ±θ1\pmθ_1 and ±θ2\pmθ_2 respectively, then every (12mn+1)(\frac{1}{2}mn+1)-vertex induced subgraph of Γ1□~Γ2Γ_1\widetilde{\Box}Γ_2 (resp. Γ1⋈~Γ2Γ_1\widetilde{\bowtie} Γ_2) has maximum degree at least θ12+θ22\sqrt{θ_1^2+θ_2^2} (resp. (θ12+1)θ22\sqrt{(θ_1^2+1)θ_2^2}). Moreover, we discuss the eigenvalues of Γ1□~Γ2Γ_1\widetilde{\Box} Γ_2 and Γ1⋈~Γ2Γ_1\widetilde{\bowtie} Γ_2 and obtain a sufficient and necessary condition such that the spectrum of Γ1□~Γ2Γ_1\widetilde{\Box}Γ_2 and Γ1⋈~Γ2Γ_1\widetilde{\bowtie}Γ_2 are symmetric, from which we obtain more general results on maximum degree of the induced subgraphs.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.