2020/01/03 by Zhen‐Mu Hong, Hong‐Jian Lai, Hong, Zhen-Mu +2 · 2 citations
Computer Science · Mathematics · #05C22 #05C50 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2001.00730
openalex publication_date 2020/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently, Huang showed that every (2n-1+1)-vertex induced subgraph of the n-dimensional hypercube has maximum degree at least √(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 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\widetilde\BoxΓ2 and Γ1\widetilde\bowtie Γ2, we show that if Γ1 and Γ2 have exactly two distinct adjacency eigenvalues ±θ1 and ±θ2 respectively, then every ((1)/(2)mn+1)-vertex induced subgraph of Γ1\widetilde\BoxΓ2 (resp. Γ1\widetilde\bowtie Γ2) has maximum degree at least √(θ12+θ22) (resp. √((θ12+1)θ22)). Moreover, we discuss the eigenvalues of Γ1\widetilde\Box Γ2 and Γ1\widetilde\bowtie Γ2 and obtain a sufficient and necessary condition such that the spectrum of Γ1\widetilde\BoxΓ2 and Γ1\widetilde\bowtieΓ2 are symmetric, from which we obtain more general results on maximum degree of the induced subgraphs.