论文标题
产品图的诱导子图和黄定理的概括
Induced subgraphs of product graphs and a generalization of Huang's theorem
论文作者
论文摘要
最近，黄表明，每$（2^{n-1} +1）$ - 顶点诱导的$ n $二维超轴的子图具有最高学位，至少$ \ sqrt {n} $在[数学年鉴，190（2019），2019年（2019年），949---955]。在本文中，我们讨论了笛卡尔产品图和半肌产品图的诱导子图，以概括黄的结果。令$γ_1$为连接的签名的订单$ n $的签名二角图，$γ_2$是订单$ m $的连接签名图。通过定义$γ_1$和$γ_2$的两种签名产品，由$γ_1\ widetilde {\ box}γ_2$和$γ_1\ widetilde {\ bowtie}γ_2$，我们表明，如果$γ_1$和$γ_2$ eig， $ \pmθ_2$分别，然后每个$（\ frac {1} {2} mn+1）$ - 顶点诱导的子图的$γ_1\ widetilde {\ box}γ_2$（sives.up $γ_1 $ \ sqrt {θ_1^2+θ_2^2} $（resp。$ \ sqrt {（θ_1^2+1）θ_2^2} $）。此外，我们讨论了$γ_1\ widetilde {\ box}γ_2$和$γ_1\ widetilde {\ bowtie}γ_2$的特征值，并获得足够和必要的条件，使得$γ_1\ \ \ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ $γ_1\ widetilde {\ bowtie}γ_2$是对称的，从中，我们从最大程度的诱导子图中获得了更一般的结果。
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 $Γ_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 $\pmθ_1$ and $\pmθ_2$ respectively, then every $(\frac{1}{2}mn+1)$-vertex induced subgraph of $Γ_1\widetilde{\Box}Γ_2$ (resp. $Γ_1\widetilde{\bowtie} Γ_2$) has maximum degree at least $\sqrt{θ_1^2+θ_2^2}$ (resp. $\sqrt{(θ_1^2+1)θ_2^2}$). 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.
