Positive and negative inertia index of a hypertree
-
Abstract: This paper extend the conclusion of the graph to hypergraphs, prove that the positive and negative inertia index of a single hypertree are related to the number of hyperedges and vertices, and give the positive and negative inertia index of two hypertrees connected by a hyperedge.
-
Keywords:
- hypertree /
- positive inertia index /
- negative inertia index
-
0. 引言
超图$ \mathcal{G}=\left(V, E\right) $是由非空顶点集$ V=V\left(\mathcal{G}\right) $和边集$ E=E\left(\mathcal{G}\right) $组成的,这里的每条边$ e\in E\left(\mathcal{G}\right) $是至少包含2个顶点的$ V\left(\mathcal{G}\right) $的子集。$ \left|V\left(\mathcal{G}\right)\right|=n $和$ \left|E\left(\mathcal{G}\right)\right|=m $表示超图$ \mathcal{G} $的顶点和超边个数。本文中超图$ \mathcal{G} $的每条超边大小都为$ k $时,把超图$ \mathcal{G} $称作是$ k- $一致的。众所周知,$ 2- $一致超图总是称作普通图。含有$ n $个顶点的完全图记作$ {K}_{n} $。
对于一个超图$ \mathcal{G} $,定义超图$ \mathcal{G}-{v}_{0} $是从$ \mathcal{G} $中删去顶点$ {v}_{0} $以及删去与$ {v}_{0} $相关联的超边所得。对于一个顶点集$ S\in V\left(\mathcal{G}\right) $,定义超图$ \mathcal{G}-S $是从$ \mathcal{G} $中删去$ S $中的所有顶点以及删去与$ S $中的任意一个顶点相关联的超边所得。
在一个超图中,如果2个顶点包含在同一条超边上,则这2个顶点是相邻的。如果2条超边的交非空,则这2条超边相邻。如果$ v\in e $,则超边$ e $与一个顶点$ v $是关联的。在超图$ \mathcal{G} $中,顶点$ v $的度$ \mathrm{deg}_{\mathcal{G}}\left(v\right) $称作是与顶点$ v $所关联的超边个数。对于一个超图$ \mathcal{G} $,分别记$ \varDelta \left(\mathcal{G}\right) $和$ \delta \left(\mathcal{G}\right) $为最大度和最小度。其中度为1的顶点称作悬挂点。至多有1个顶点的度 > 1且在这条超边的其他顶点的度都是悬挂点的超边称作悬挂边。
在一个超图中,长度为$ q $的超路径$ {v}_{1}{e}_{1}{v}_{2}{e}_{2}\cdots {v}_{q}{e}_{q}{v}_{q+1} $被定义作顶点和超边的交替序列,使得$ {v}_{1}, {v}_{2}, \cdots , {v}_{q+1} $是不同的顶点,$ {e}_{1}, {e}_{2}, \cdots , {e}_{q} $是不同的超边。对于$ i=\mathrm{1, 2}, \cdots , q, {v}_{i}, {v}_{i+1}\in {e}_{i} $,对于$ i=\mathrm{1, 2}, \cdots , q-1, $ $ {e}_{i}\bigcap {e}_{i+1}={v}_{i+1} $,如果$ \left|i-j\right|\le $2,则$ {e}_{i}\bigcap {e}_{j}=\varnothing $成立。长度为$ q $的超圈$ {v}_{1}{e}_{1}{v}_{2}{e}_{2}\cdots {v}_{q}{e}_{q}{v}_{1} $是从一条超路径$ {v}_{1}{e}_{1}{v}_{2}{e}_{2}\cdots {v}_{q}{e}_{q}{v}_{q+1} $中在$ {v}_{1} $和$ {v}_{q} $之间添加一条新的超边$ {e}_{q} $所得,其中$ {e}_{q}\bigcap {e}_{1}=\left\{{v}_{1}\right\}, {e}_{q}\bigcap {e}_{q-1}=\left\{{v}_{q}\right\} $,如果$ j\ne 1, q-1 $,$ \left|q-j\right|\ge 2 $成立,则$ {e}_{i}\bigcap {e}_{j}=\varnothing $。对于所有的$ u, v\in V\left(\mathcal{G}\right) $,如果存在从$ v $到$ u $的超路径,则该超图$ \mathcal{G} $是连通的。如果超图$ \mathcal{G} $不包含超圈,则该超图$ \mathcal{G} $是无圈的。
Cioaba等[1]定义了超图$ \mathcal{G} $的邻接矩阵$ \boldsymbol A $,邻接矩阵定义为
$$ {\boldsymbol A}_{x, y}=\left\{\begin{array}{ll}\left|\left\{e\in E:\left\{x, y\right\}\subset e\right\}\right|, & x\ne y, \\ 0, & x=y。\end{array}\right. $$ $ \boldsymbol A $的特征值$ {\lambda }_{1}, {\lambda }_{2}, \cdots , {\lambda }_{n} $是超图$ \mathcal{G} $的特征值,并且其形成了超图的谱。实对称矩阵$ \boldsymbol A $的谱中正特征值、负特征值、零特征值的个数称为正惯性指数、负惯性指数、零度,用$ p\left(\boldsymbol A\right) $、$ q\left(\boldsymbol A\right) $、$ \eta \left(\boldsymbol A\right) $表示。对于一个超图$ \mathcal{G} $,其邻接矩阵为$ \boldsymbol A\left(\mathcal{G}\right) $,分别称$ p\left(\boldsymbol A\left(\mathcal{G}\right)\right) $、$ q\left(\boldsymbol A\left(\mathcal{G}\right)\right) $和$ \eta \left(\boldsymbol A\left(\mathcal{G}\right)\right) $是$ \mathcal{G} $的正惯性指数、负惯性指数和零度,为了简便,将其写为$ p\left(\mathcal{G}\right) $、$ q\left(\mathcal{G}\right) $和$ \eta \left(\mathcal{G}\right) $。显然,$ p\left(\mathcal{G}\right)+q\left(\mathcal{G}\right)+\eta \left(\mathcal{G}\right)=\left|V\left(\mathcal{G}\right)\right| $。
图惯性的研究由于其在化学中的许多应用而引起广泛关注[2-5]。Gregory等[6]研究了正负惯性指数的次加性,并发展了厄米秩的一些性质,得到了双方分解数的一些结果;Gregory等[7]研究了2个图的部分连接的惯性,并建立了图的部分连接的惯性与双式分解之间的一些关系;Daughert[8]用匹配数对单圈图的惯性进行了刻画,得到了一个计算其线性时间算法;Torgašev[9]给出了顶点集上的一个等价关系,并将G的标准图定义为相应的商图,其推导出所有具有恰好$ n\left(\ge 1\right) $个负特征值(包括多重性)的连通图的类只包含有限多个所谓的正则图;Torgašev[10]得到了一个有限连通图G恰好有2个负特征值,当且仅当其正则图是9个特定图中的一个,每个图都有3、4、5或6个顶点,此外还建立了第2和3个的最小负特征值的严格上界;Yu等[11]刻画了有1或者2个正特征值的符号树、符号单圈图、符号双圈图;Ma等[12]研究了树、单圈图、双圈图的正负惯性指数,得到了其计算方法,并证明了正负惯性指数差的一个不等式;Ma等[13]研究了树的线图的正负惯性指数,得到了树的线图的正惯性指数界与树中的非悬挂边的个数有关,证明了当树的线图的正惯性指数达到上界时,树的线图是非奇异的,而当树的线图的正惯性指数达到下界时,树的线图是奇异的;Duan[14]研究了符号图的惯性指数和基底图的惯性指数的关系;Ma和Xie[15]研究了一种特殊的三圈图的惯性指数,给出了一种计算具有较大顶点的三圈图惯性指数的新方法;Yu等[16]研究了所有带有悬挂顶点的$ n $阶双圈图之间的最小正惯性指数,并刻画了所有$ n $阶双圈图中正惯性指数为1或2的双圈图。基于上述讨论,研究超图的正负惯性指数将是有趣的。
1. 定义和引理
在这一节中,本文引用一些以前的结果。假设$ \boldsymbol A, \boldsymbol B $是2个$ n $阶的实对称矩阵,若存在一个$ n $阶的可逆矩阵$ \boldsymbol P $,使得$ {\boldsymbol P}^{\rm T}\boldsymbol A\boldsymbol P=\boldsymbol B $,则说$ \boldsymbol A $和$ \boldsymbol B $是合同的,记作$ \boldsymbol A\simeq \boldsymbol B $。
定义1[17] 超树是一个既连通又无圈的超图。
Berge[18]给出了无圈超图的一个刻画,特别是对于连通的情况,结果如下。
引理2[18] 如果$ \mathcal{G} $是一个有$ n $个顶点和$ m $条超边的连通超图,则$ \mathcal{G} $是无圈的当且仅当$ {\sum }_{i\in \left[m\right]}\left|{e}_{i}-1\right|=n-1 $。
引理3[19] $ \boldsymbol A, \boldsymbol B $是2个$ n $阶的实对称矩阵,使得$ \boldsymbol A\simeq \boldsymbol B $。则$ p\left(\boldsymbol A\right)=p\left(\boldsymbol B\right) $,$ n\left(\boldsymbol A\right)=n\left(\boldsymbol B\right) $,$ \eta \left(A\right)=\eta \left(\boldsymbol B\right) $。
引理4[13] 令$ \boldsymbol A=\left[{a}_{ij}\right] $是一个$ 2\times 2 $的非奇异的实对称矩阵,如果$ {a}_{22}=0 $,则$ p\left(\boldsymbol A\right)=n\left(\boldsymbol A\right)=1 $。
引理5[13] 如果$ m\ge $2,$ {K}_{m} $的特征值是$ m-1 $和$ -1 $(重数为$ m-1 $),则$ p\left({K}_{m}\right)=1 $,$ n\left({K}_{m}\right)=m-1 $。
2. 主要结论
引理6 设$ T $是含有$ n $个顶点,$ m $条超边大小为$ {k}_{i}\left(i=\mathrm{1, 2}, \cdots , m, 且{k}_{i}\ge 3\right) $的超树,若超树$ T $满足以下2个条件之一:
(1)如果超树$ H $是非奇异的,$ H-{v}_{0} $是奇异的,存在1个顶点$ {v}_{1}\in V\left(H\right) $,$ {v}_{1}\ne {v}_{0} $,使得$ H-{v}_{0}-{v}_{1} $是非奇异的;
(2)$ H-{v}_{0} $是非奇异的,如果$ \frac{\left|H\right|}{|H-{v}_{0}|}=\frac{{k}_{m}-1}{{k}_{m}-2} $或$ \frac{\left|H\right|}{|H-{v}_{0}|}\le 0 $时,则超树$ T $的正负惯性指数分别为$ p\left(T\right)=m $,$ q\left(T\right)=n-m $。
证明 对超边的个数$ m $进行归纳。
(1)当$ m=1 $时,$ n={k}_{1}\left({k}_{1}\ge 3\right) $,此时超树$ T $为$ n $个顶点一条超边的超树,对应的邻接矩阵为
$$ \boldsymbol A=\boldsymbol A\left(T\right)=\left[\begin{array}{cc}\boldsymbol J-\boldsymbol I& \boldsymbol j\\ {\boldsymbol j}^{\rm T}& 0\end{array}\right] \text{,} $$ 式中$ \boldsymbol J $、$ \boldsymbol I $、$ \boldsymbol j $分别表示$ {k}_{1}-1 $阶的全1方阵、单位矩阵、全1列向量。
取$ \boldsymbol Q=\left[\begin{array}{cc}\boldsymbol I& -{\left(\boldsymbol J-\boldsymbol I\right)}^{-1}\boldsymbol j\\ {\mathit{\pmb{0}}}^{\rm T}& 1\end{array}\right] $,有$ {\boldsymbol Q}^{\rm T}\boldsymbol A\boldsymbol Q=\left[\begin{array}{cc}\boldsymbol J-\boldsymbol I& \mathit{\pmb{0}}\\ {\mathit{\pmb{0}}}^{\rm T}& -\frac{{k}_{1}- 1}{{k}_{1}- 2}\end{array}\right] $,其中$ -\frac{{k}_{1}-1}{{k}_{1}-2} < 0 $。
由引理3可知,如果$ \boldsymbol A $和$ \boldsymbol B $是2个合同的实对称矩阵,那么矩阵$ \boldsymbol A $和$ \boldsymbol B $有相同的正负惯性指数,又根据引理5,$ \boldsymbol J-\boldsymbol I $是完全图$ {K}_{{k}_{1}-1} $对应的邻接矩阵,并且其正负惯性指数分别为$ p\left(\boldsymbol J-\boldsymbol I\right)=1 $,$ q\left(\boldsymbol J-\boldsymbol I\right)={k}_{1}-2 $。因此,$ p\left(\boldsymbol A\right)=1 $,$ q\left(\boldsymbol A\right)={k}_{1}-1 $,结论成立。
(2)假设超边个数为$ m-1 $时结论成立。
(3)当超边个数为$ m $时,超树$ T $可看作是有$ m-1 $条超边的超树$ H $通过其顶点$ {v}_{0} $标记$ {K}_{{k}_{m}}\left({k}_{m}\ge 3\right) $的一个顶点得到的,记作$ T={K}_{{k}_{m}}△\left({v}_{0}\right)H $。
当条件(1)成立时,超树$ T={K}_{{k}_{m}}△\left({v}_{0}\right)H $的邻接矩阵为
$$ \begin{array}{c} \boldsymbol A=\boldsymbol A\left(T\right)=\\ \left[\begin{array}{cccc}\boldsymbol J-\boldsymbol I& {\boldsymbol j}_{({k}_{m}-1)\times 1}& {\mathit{\pmb{0}}}_{({k}_{m}-1)\times 1}& \mathit{\pmb{0}}\\ {\boldsymbol j}_{1\times ({k}_{m}-1)}^{\rm T}& 0& \delta & {\boldsymbol \alpha }_{1\times (n-{k}_{m}-1)}^{\rm T}\\ {\mathit{\pmb{0}}}_{1\times ({k}_{m}-1)}^{\rm T}& \delta & 0& {\boldsymbol \beta }_{1\times (n-{k}_{m}-1)}^{\rm T}\\ {\mathit{\pmb{0}}}_{(n-{k}_{m}-1)\times ({k}_{m}-1)}^{\rm T}& {\boldsymbol \alpha }_{(n-{k}_{m}-1)\times 1}& {\boldsymbol \beta }_{(n-{k}_{m}-1)\times 1}& \boldsymbol B\end{array}\right] \text{,} \end{array} $$ 其中$ \delta =\left\{\begin{array}{l}1, {v}_{0}~{v}_{1}\\ 0, 否则\end{array}\right. $,$ \boldsymbol \alpha $和$ \boldsymbol \beta $分别为顶点$ {v}_{0} $和$ {v}_{1} $与$ H-{v}_{0}-{v}_{1} $的顶点的邻接关系向量,$ \boldsymbol B $是$ H-{v}_{0}-{v}_{1} $的邻接矩阵。
由假设知,$ H-{v}_{0}-{v}_{1} $非奇异,即$ \boldsymbol B $可逆。取
$$ \boldsymbol Q=\left[\begin{array}{cccc}{\boldsymbol I}_{{k}_{m}-1}& -{\left(\boldsymbol J-\boldsymbol I\right)}^{-1}\boldsymbol j& {\mathit{\pmb{0}}}_{({k}_{m}-1)\times 1}& {\mathit{\pmb{0}}}_{({k}_{m}-1)\times (n-{k}_{m}-1)}\\ {\mathit{\pmb{0}}}_{1\times ({k}_{m}-1)}& 1& 0& {\mathit{\pmb{0}}}_{1\times (n-{k}_{m}-1)}\\ {\mathit{\pmb{0}}}_{1\times ({k}_{m}-1)}& 0& 1& {\mathit{\pmb{0}}}_{1\times (n-{k}_{m}-1)}\\ {\mathit{\pmb{0}}}_{(n-{k}_{m}-1)\times ({k}_{m}-1)}& -{\boldsymbol B}^{-1}\boldsymbol \alpha & -{\boldsymbol B}^{-1}\boldsymbol \beta & {\boldsymbol I}_{n-{k}_{m}-1}\end{array}\right] \text{,} $$ 根据合同变换,有
$$ \begin{array}{c}{\boldsymbol Q}^{\rm T}\boldsymbol A\boldsymbol Q=\\ \left[\begin{array}{cccc}\boldsymbol J-\boldsymbol I& {\mathit{\pmb{0}}}_{({k}_{m}-1)\times 1}& {\mathit{\pmb{0}}}_{({k}_{m}-1)\times 1}& {\mathit{\pmb{0}}}_{1\times (n-{k}_{m}-1)}^{\rm T}\\ {\mathit{\pmb{0}}}_{1\times ({k}_{m}-1)}^{\rm T}& -\frac{{k}_{m}- 1}{{k}_{m}- 2}-{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta & {\mathit{\pmb{0}}}_{1\times (n-{k}_{m}-1)}^{\rm T}\\ {\mathit{\pmb{0}}}_{1\times ({k}_{m}-1)}^{\rm T}& \delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta & {\mathit{\pmb{0}}}_{1\times (n-{k}_{m}-1)}^{\rm T}\\ {\mathit{\pmb{0}}}_{(n-{k}_{m}-1)\times ({k}_{m}-1)}& {\mathit{\pmb{0}}}_{(n-{k}_{m}-1)\times 1}& {\mathit{\pmb{0}}}_{(n-{k}_{m}-1)\times 1}& \boldsymbol B\end{array}\right] 。 \end{array}$$ 因为$ H-{v}_{0} $是奇异的,由$ \left[\begin{array}{cc}0& {\boldsymbol \beta }^{\rm T}\\ \boldsymbol \beta & \boldsymbol B\end{array}\right] $合同于$ \left[\begin{array}{cc}-{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta & \mathit{\pmb{0}}_{1\times (n-{k}_{m}-1)}^{\rm T}\\ \mathit{\pmb{0}}_{(n-{k}_{m}-1)\times 1}& \boldsymbol B\end{array}\right] $,故$ \left[\begin{array}{cc}-{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta & \mathit{\pmb{0}}_{1\times (n-{k}_{m}-1)}^{\rm T}\\ \mathit{\pmb{0}}_{(n-{k}_{m}-1)\times 1}& \boldsymbol B\end{array}\right] $奇异,因此$ -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta =0 $。
现考虑超树$ H $的邻接矩阵$ \boldsymbol A\left(H\right)=\left[\begin{array}{ccc}0& \delta & {\boldsymbol \alpha }^{\rm T}\\ \delta & 0& {\boldsymbol \beta }^{\rm T}\\ \boldsymbol \alpha & \boldsymbol \beta & \boldsymbol B\end{array}\right] $,使得
$$ \boldsymbol A\left(H\right)\simeq \left[\begin{array}{ccc}-{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta & \mathit{\pmb{0}}_{1\times (n-{k}_{m}-1)}^{\rm T}\\ \delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & 0& \mathit{\pmb{0}}_{1\times (n-{k}_{m}-1)}^{\rm T}\\ \mathit{\pmb{0}}_{(n-{k}_{m}-1)\times 1}& \mathit{\pmb{0}}_{(n-{k}_{m}-1)\times 1}& \boldsymbol B\end{array}\right] 。 $$ 由假设知,$ H $是非奇异的,故
$$ -\left(\delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \right)\left(\delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha \right)\ne 0 \text{,} $$ 即
$$ \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \ne 0 。 $$ 由引理4得,
$$ \begin{array}{c} p\left(\left[\begin{array}{cc}-{\boldsymbol \alpha }^{\rm T}\boldsymbol B\boldsymbol \alpha & \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \\ \delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & 0\end{array}\right]\right)=\\q\left(\left[\begin{array}{cc}-{\boldsymbol \alpha }^{\rm T}\boldsymbol B\boldsymbol \alpha & \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \\ \delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & 0\end{array}\right]\right)=1 \text{,} \end{array}$$ 再根据$ p\left(\boldsymbol J-\boldsymbol I\right)=1 $,$ q\left(\boldsymbol J-\boldsymbol I\right)={k}_{m}-2 $,可得
$$ \begin{array}{c} p\left(\boldsymbol A\right)=p\left(\boldsymbol J-\boldsymbol I\right)+\\p\left(\left[\begin{array}{cc}-\frac{{k}_{m}-1}{{k}_{m}-2}-{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \\ \delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \end{array}\right]\right)+p\left(\boldsymbol B\right)=\\p\left(\boldsymbol B\right)+2 \text{,} \end{array}$$ $$ \begin{array}{c} q\left(\boldsymbol A\right)=q\left(\boldsymbol J-\boldsymbol I\right)+\\q\left(\left[\begin{array}{cc}-\frac{{k}_{m}-1}{{k}_{m}-2}-{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \\ \delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \end{array}\right]\right)+q\left(\boldsymbol B\right)=\\q\left(\boldsymbol B\right)+{k}_{m}-1 \text{,} \end{array}$$ 即
$$ \begin{array}{c} p\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=p\left(H-{v}_{0}-{v}_{1}\right)+2 \text{,} q\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=\\ q\left(H-{v}_{0}-{v}_{1}\right)+{k}_{m}-1 。 \end{array}$$ (1) 由
$$ p\left(H\right) =p\left(\left[\begin{array}{cc}-{\boldsymbol \alpha }^{\rm T}\boldsymbol B\boldsymbol \alpha & \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \\ \delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & 0\end{array}\right]\right)+p\left(\boldsymbol B\right) \text{,} $$ 即
$$ q\left(H\right)=q\left(\left[\begin{array}{cc}-{\boldsymbol \alpha }^{\rm T}\boldsymbol B\boldsymbol \alpha & \delta -{\boldsymbol \alpha }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \beta \\ \delta -{\boldsymbol \beta }^{\rm T}{\boldsymbol B}^{-1}\boldsymbol \alpha & 0\end{array}\right]\right)+q\left(\boldsymbol B\right) \text{,} $$ 即$ p\left(H\right)=p\left(H-{v}_{0}-{v}_{1}\right)+1 $,$ q\left(H\right)=q\left(H-{v}_{0}-{v}_{1}\right)+1 $。(2)
故由式(1和2),$ p\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=p\left(H\right)+1 $,$ q\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=q\left(H\right)+{k}_{m}-2 $。
根据归纳假设,$ p\left(H\right)=m-1 $,$ q\left(H\right)=n-\left({k}_{m}-1\right)-\left(m-1\right)=n-{k}_{m}-2 $。因此,
$$ p\left(T\right)=p\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=p\left(H\right)+1=m \text{,} $$ $$ q\left(T\right)=q\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=q\left(H\right)+{k}_{m}-2=n-m \text{,} $$ 结论成立。
当条件(2)成立时,超树$ T={K}_{{k}_{m}}△\left({v}_{0}\right)H $的邻接矩阵为
$$ \boldsymbol A=\boldsymbol A\left(T\right)=\left[\begin{array}{ccc}\boldsymbol J-\boldsymbol I& \boldsymbol j& \mathit{\pmb{0}}\\ {\boldsymbol j}^{\rm T}& 0& {\boldsymbol \gamma}^{\rm T}\\ \mathit{\pmb{0}}_{(n-{k}_{m})\times ({k}_{m}-1)}^{\rm T}& \boldsymbol \gamma& \boldsymbol C\end{array}\right] \text{,} $$ 其中$ \boldsymbol \gamma$为顶点$ {v}_{0} $与$ H-{v}_{0} $的顶点的邻接关系向量,$ \boldsymbol C $是$ H-{v}_{0} $的邻接矩阵。
由于$ H-{v}_{0} $非奇异,故$ \boldsymbol C $可逆。取
$$ \boldsymbol Q=\left[\begin{array}{ccc}\boldsymbol I& -{\left(\boldsymbol J-\boldsymbol I\right)}^{-1}\boldsymbol j& \mathit{\pmb{0}}_{({k}_{m}-1)\times (n-{k}_{m})}^{\rm T}\\ \mathit{\pmb{0}}_{1\times ({k}_{m}-1)}& 1& \mathit{\pmb{0}}_{1\times (n-{k}_{m})}^{\rm T}\\ \mathit{\pmb{0}}_{(n-{k}_{m})\times ({k}_{m}-1)}& -{\boldsymbol C}^{-1}\boldsymbol \gamma& \boldsymbol I\end{array}\right] \text{,} $$ 有
$$\begin{array}{c} {\boldsymbol Q}^{\rm T}\boldsymbol A\boldsymbol Q=\\\left[\begin{array}{ccc}\boldsymbol J-\boldsymbol I& \mathit{\pmb{0}}_{({k}_{m}-1)\times 1}& \mathit{\pmb{0}}_{({k}_{m}-1)\times (n-{k}_{m})}^{\rm T}\\ \mathit{\pmb{0}}_{1\times ({k}_{m}-1)}& -{\boldsymbol j}^{\rm T}{\left(\boldsymbol J-\boldsymbol I\right)}^{-1}\boldsymbol j-{\boldsymbol \gamma}^{\rm T}{\boldsymbol C}^{-1}\boldsymbol \gamma& \mathit{\pmb{0}}_{1\times (n-{k}_{m})}^{\rm T}\\ \mathit{\pmb{0}}_{(n-{k}_{m})\times ({k}_{m}-1)}& \mathit{\pmb{0}}_{(n-{k}_{m})\times 1}& \boldsymbol C\end{array}\right] \text{,}\end{array} $$ 其中
$$ -{\boldsymbol \gamma}^{\rm T}{\boldsymbol C}^{-1}\boldsymbol \gamma=\frac{\left|H\right|}{\left|\boldsymbol C\right|}=\frac{\left|H\right|}{|H-{v}_{0}|} \text{,} {\boldsymbol j}^{\rm T}{\left(\boldsymbol J-\boldsymbol I\right)}^{-1}\boldsymbol j=\frac{{k}_{m}- 1}{{k}_{m}- 2} 。 $$ 若$ \frac{\left|H\right|}{|H-{v}_{0}|}=\frac{{k}_{m}- 1}{{k}_{m}- 2} $,则
$$ -{\boldsymbol j}^{\rm T}{\left(\boldsymbol J-\boldsymbol I\right)}^{-1}\boldsymbol j-{\boldsymbol \gamma}^{\rm T}{\boldsymbol C}^{-1}\boldsymbol \gamma> 0 \text{,} $$ 从而可得
$$ p\left(\boldsymbol A\right)=p\left(\boldsymbol J-\boldsymbol I\right)+p\left(\boldsymbol C\right)+1=p\left(\boldsymbol C\right)+2 \text{,} $$ $$ q\left(\boldsymbol A\right)=q\left(\boldsymbol J-\boldsymbol I\right)+q\left(\boldsymbol C\right)=q\left(\boldsymbol C\right)+{k}_{m}-2 \text{,} $$ 等价于
$$ p\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=p\left(H-{v}_{0}\right)+2 \text{,} $$ $$ q\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=q\left(H-{v}_{0}\right)+{k}_{m}-2 。 $$ 另外,
$$ \boldsymbol A\left(H\right) =\left[\begin{array}{cc}0& {\boldsymbol \gamma}^{\rm T}\\ \boldsymbol \gamma& \boldsymbol C\end{array}\right] \text{,} \boldsymbol A\left(H\right) =\left[\begin{array}{cc}-{\boldsymbol \gamma}^{\rm T}{\boldsymbol C}^{-1}\boldsymbol \gamma& \mathit{\pmb{0}}_{1\times (n-{k}_{m})}^{\rm T}\\ \mathit{\pmb{0}}_{(n-{k}_{m})\times 1}& \boldsymbol C\end{array}\right] 。 $$ 于是有
$$ p\left(H\right)=p\left(H-{v}_{0}\right)+1 \text{,} $$ $$ q\left(H\right)=q\left(H-{v}_{0}\right)=n-{k}_{m}-p\left(H-{v}_{0}\right) 。 $$ 根据归纳假设,可得
$$ p\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=p\left(H\right)+1=m \text{,} $$ $$ \begin{array}{c}q\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=\\ n-{k}_{m}-p\left(H-{v}_{0}\right)+{k}_{m}-2=\\ n-2-p\left(H-{v}_{0}\right)=\\ n-2-\left(p\left(H\right)-1\right)=\\ n-p\left(H\right)-1=n-m。\end{array} $$ 若$ \frac{\left|H\right|}{|H-{v}_{0}|}\le 0 $时,$ -{\boldsymbol j}^{\rm T}{(\boldsymbol J-\boldsymbol I)}^{-1}\boldsymbol j-{\boldsymbol \gamma}^{\rm T}{\boldsymbol C}^{-1}\boldsymbol \gamma=\frac{\left|H\right|}{|H-{v}_{0}|}-\frac{{k}_{m}-1}{{k}_{m}-2} < 0 $,从而可得,
$$ p\left(\boldsymbol A\right)=p(\boldsymbol J-\boldsymbol I) +p\left(\boldsymbol C\right) =p\left(\boldsymbol C\right) +1 \text{,} $$ $$ q\left(\boldsymbol A\right) =q(\boldsymbol J-\boldsymbol I) +q\left(\boldsymbol C\right) +1 =q\left(\boldsymbol C\right) +{k}_{m}- 1 。 $$ 等价于
$$ p\left({K}_{{k}_{m}}\Delta \right({v}_{0}\left)H\right)=p(H-{v}_{0})+1 \text{,} $$ $$ q\left({K}_{{k}_{m}}\Delta \right({v}_{0}\left)H\right)=q(H-{v}_{0})+{k}_{m}-1 。 $$ 又因为
$$ \boldsymbol A\left(H\right)=\left[\begin{array}{cc}{\bf 0}& {\boldsymbol \gamma}^{\rm T}\\ \boldsymbol \gamma& \boldsymbol C\end{array}\right] \text{,} \boldsymbol A\left(H\right) \simeq \left[\begin{array}{cc}-{\boldsymbol \gamma}^{\rm T}{\boldsymbol C}^{-1}\boldsymbol \gamma& \mathit{\pmb{0}}_{1\times (n-{k}_{m})}^{\rm T}\\ \mathit{\pmb{0}}_{(n-{k}_{m})\times 1}& \boldsymbol C\end{array}\right] 。 $$ 于是有
$$ p\left(H\right)=p(H-{v}_{0}) \text{,} $$ $$ q\left(H\right)=q(H-{v}_{0})+1=n-{k}_{m}-p(H-{v}_{0})+1 。 $$ 根据归纳假设,可得
$$ p\left({K}_{{k}_{m}}\Delta \right({v}_{0}\left)H\right)=p\left(H\right)+1=m \text{,} $$ $$ \begin{array}{c}q\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=q\left(H\right)+{k}_{m}-2=\\ n-{k}_{m}-p\left(H-{v}_{0}\right)+1+{k}_{m}-2=\\ n-p\left(H-{v}_{0}\right)-1=\\ n-p\left(H\right)-1=n-m。\end{array} $$ 综上所述,若超树$ T $满足引理中2个条件之一,则超树$ T $的正负惯性指数分别为$ p\left(T\right)=m $,$ q\left(T\right)=n-m $。
定理7 设$ {T}_{1} $是含有$ {n}_{1} $个顶点,$ {m}_{1} $条超边大小为$ {k}_{i}\left(i=\mathrm{1, 2}, \cdots , {m}_{1}, 且{k}_{i}\ge 3\right) $的超树,$ {T}_{2} $是含有$ {n}_{2} $个顶点,$ {m}_{2} $条超边大小为$ {k}_{j}\left(j=\mathrm{1, 2}, \cdots , {m}_{2}, 且{k}_{j}\ge 3\right) $的超树,并且$ {T}_{1} $和$ {T}_{2} $不相交。若$ T $是在$ {T}_{1} $和$ {T}_{2} $之间加一条大小为$ k\left(k\ge 3\right) $超边所得的超树,并且$ T $、$ {T}_{1} $和$ {T}_{2} $分别满足引理6中2个条件之一,则
$$ p\left(T\right)=p\left({T}_{1}\right)+p\left({T}_{2}\right)+1={m}_{1}+{m}_{2}+1 \text{,} $$ $$ q\left(T\right)=n-{m}_{1}-{m}_{2}-1 。 $$ 证明 令$ T={K}_{{k}_{m}}△\left({v}_{0}\right)H $,其中$ {k}_{m} $是$ {T}_{i} $ $ \left(i=\mathrm{1, 2}\right) $中一条超边的大小,$ H $是包含顶点$ {v}_{0} $的含有$ {m}_{1}+{m}_{2} $条超边的超树,使用引理6可知,$ p\left({T}_{1}\right)={m}_{1} $,$ q\left({T}_{1}\right)={n}_{1}-{m}_{1} $,$ p\left({T}_{2}\right)={m}_{2} $,$ q\left({T}_{2}\right)={n}_{2}-{m}_{2} $,$ p\left(T\right)=p\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)={m}_{1}+{m}_{2}+1 $,$ q\left(T\right)=q\left({K}_{{k}_{m}}△\left({v}_{0}\right)H\right)=n-{m}_{1}-{m}_{2}- 1 $,其中$ n={n}_{1}+{n}_{2}+{k}_{m}- 2 $。
3. 结束语
本文将图上的结论推广到了超图上,并证明了单个超树的正负惯性指数与超边个数和顶点个数有关,其次推出了2个超树通过一条超边连接后的超树的正惯性指数问题。本文的研究方法对于研究超树的线图、符号超图及符号超图的线图的正负惯性指数问题提供思路和方法。
-
[1] CIOAB S M, KOOLEN J H, MIMURA M, et al. On the spectrum and linear programming bound for hypergraphs[J]. European Journal of Combinatorics, 2022, 104: 103535. doi: 10.1016/j.ejc.2022.103535 [2] COLLATZ L, SINOGOWITZ U. Spectra of finite graphs[J]. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 1957, 21: 64-77. [3] FOWLER P W, MANOLOPOULOS D E. An atlas of fullerenes[M]. Oxford: Clarendon Press, 1995. [4] CVETKOVIĆ D, GUTMAN I, TRINAJSTIĆ N. Graph theory and molecular orbitals. Ⅱ[J]. Theoretical Chemistry Accounts, 1972, 34(2): 129-136. [5] LONGUET-HIGGINS H C. Some studies in molecular orbital theory I. Resonance structures and molecular orbitals in unsaturated hydrocarbons[J]. The Journal of Chemical Physics, 1950, 18(3): 265-274. doi: 10.1063/1.1747618 [6] GREGORY D A, WATTS V L, SHADER B L. Biclique decompositions and Hermitian rank[J]. Linear Algebra and its Applications, 1999, 292(1/2/3): 267-280. [7] GREGORY D A, HEYINK B, VANDER MEULEN K N. Inertia and biclique decompositions of joins of graphs[J]. Combination Theory Series B, 2003, 88: 135-151. doi: 10.1016/S0095-8956(02)00041-2 [8] DAUGHERTY S. The inertia of unicyclic graphs and the implications for closed-shells [J]. Linear Algebra and its Applications, 2008, 429(4): 849-858. doi: 10.1016/j.laa.2008.04.013 [9] TORGŠEV A. On graphs with a fixed number of negative eigenvalues[J]. Discrete Math, 1985, 57(3): 311-317. doi: 10.1016/0012-365X(85)90184-0 [10] TORGŠEV A. Graphs with exactly two negative eigenvalues[J]. Mathematische Nachrichten, 1985, 122: 135-140. doi: 10.1002/mana.19851220113 [11] YU G H, FENG L H, QU H. Signed graphs with small positive index of inertia[J]. The Electronic Journal of Linear Algebra ELA, 2016, 31: 232-243. doi: 10.13001/1081-3810.1976 [12] MA H C, YANG W H, LI S G. Positive and negative inertia index of a graph[J]. Linear Algebra and its Applications, 2013, 438(1): 331-341. doi: 10.1016/j.laa.2012.07.014 [13] MA X B, WONG D, ZHU M. The positive and the negative inertia index of line graphs of trees[J]. Linear Algebra and its Applications, 2013, 439(10): 3120-3128. doi: 10.1016/j.laa.2013.08.024 [14] DUAN F. The inertia indices of a signed graph in terms of the inertia indices of its underlying graph[J]. Linear and Multilinear Algebra, 2020, 70(3): 497-510. [15] MA H C, XIE C L. The inertia indexes of one special kind of tricyclic graphs[J]. Applied Mathematics, 2019, 10(1): 11-18. doi: 10.4236/am.2019.101002 [16] YU G H, FENG L H, WANG Q W. Bicyclic graphs with small positive index of inertia[J]. Linear Algebra and its Applications, 2013, 438(5): 2036-2045. doi: 10.1016/j.laa.2012.09.031 [17] ZHANG L, HOU Y P. Nodal domain theorem of signed hypergraphs[EB/OL]. [2023-07-02]. https://arxiv.org/abs/2207.02664. [18] BERGE C. Graphs and hypergraphs[M]. 2nd ed. Amsterdam: North Holland Publishing Company, 1976. [19] LANCASTER P, TISMENETSKY M. The theory of matrices with application[M]. Orlando Florida: Academic Press, 1985.