关于自环图能量的新下界

New Lower Bounds on the Energy of Graphs with Self-Loops

摘要: 设$G_S$ 为$n$ 个顶点的自环图，其通过在简单图$G$ 上向点集$S\subseteq V\left(G\right)$ 中的点添加自环得到。自环图$G_S$ 的能量由Gutman等学者定义为$E\left(G_S\right)={\displaystyle {\sum }_{i=\text{1}}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|}$ ，其中${\lambda }_{\text{1}},\cdots ,{\lambda }_n$ 为$G_S$ 的邻接特征值，$\sigma$ 为$G_S$ 中自环的个数。本文利用矩阵理论给出了一个自环图最大特征值上界的充要条件，并利用这个上界和Ozeki不等式分别给出了自环图能量$E\left(G_S\right)$ 的新下界。

Abstract: Let $G_S$ be a self-loop graph with $n$ vertices obtained from a simple graph $G$ by attaching one self-loop at each vertex in $S\subseteq V\left(G\right)$ . The energy of a self-loop graph $G_S$ is defined by Gutman et al. as $E\left(G_S\right)={\displaystyle {\sum }_{i=\text{1}}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|}$ , where ${\lambda }_{\text{1}},\cdots ,{\lambda }_n$ are the adjacency eigenvalues of $G_S$ and $\sigma$ is the number of self-loops of $G_S$ . In this paper, the sufficient and necessary conditions for the upper bound of the maximum eigenvalue of a self-loop graph are given. Moreover, new lower bounds on the energy of graphs with self-loops $E\left(G_S\right)$ are obtained by using this upper bound and Ozeki’s inequality, respectively.

1. 引言

图能量相关的研究起源于Hückel分子轨道理论(HMO)，由德国学者Erich Hückel提出。共轭碳氢化合物形成过程中产生的能量为总的π-电子能量，而总的π-电子能量的计算公式为其分子图所有特征值的绝对值之和。目前，简单图能量的定义普遍采用Gutman于1978年在[1]中的定义：$E\left(G\right)={\displaystyle {\sum }_{i=1}^n\left|{\lambda }_i\right|}$ ，其中${\lambda }_1,\dots ,{\lambda }_n$ 为简单图$G$ 的邻接特征值。图能量是图谱理论与化学图论中的一个重要指标，文献[2]指出烷烃的各种物理化学性质与图能量的相关性与其他传统分子结构描述符(例如Wiener指数和连通性指数)的相关性呈现相似的结果；文献[3]则通过图能量和图的谱距研究了基于熵的图测度的极值结果。图能量理论与博弈论也存在一定的联系，文献[4]指出了图能量理论可以在合作博弈论的视角下得到充分的解释。更多有关图能量的相关背景与细节可查看著作[5]。

有关图能量上下界的研究一直是国内外学者的重要研究课题。1971年，McClelland在文献[6]中通过Frobenius范数和柯西不等式对拉格朗日恒等式进行放缩，从而首次给出了图能量的上界$E\left(G\right)\le \sqrt{2mn}$ ，其中$m,n$ 分别表示简单图$G$ 的边数与点数，这一类型的上界被后人归纳为McClelland型上界，同时McClelland也利用特征值的性质在文献[6]中给出了一类与简单图$G$ 的邻接矩阵行列式相关的下界$E\left(G\right)\ge \sqrt{2m+n\left(n-1\right){\left|\det A\right|}^{\frac{2}{n}}}$ ，这一类型的下界也被后人归纳为McClelland型下界。1999年，Caporossi等学者在McClelland工作的基础上在文献[7]中给出了只与边数相关的上下界：$2\sqrt{m}\le E\left(G\right)\le 2m$ 。2001年，Koolen与Moulton在文献[8]给出了一类只与边数与点数相关的上界$E\left(G\right)\le \frac{2m}{n}+\sqrt{\left(n-1\right)\left[2m-{\left(\frac{2m}{n}\right)}^2\right]}$ ，这一上界被归纳为Koolen-Moulton型上界。2016年，Agudelo与Rada在文献[9]中将McClelland型下界从简单图推广至有向图。2022年，Gutman等学者在文献[10]中首次将图能量这一概念从简单图推广到自环图中；除此之外，他们将McClelland型上界从简单图推广至自环图：$E\left(G_S\right)\le \sqrt{n\left(2m+\sigma -\frac{{\sigma }^2}{n}\right)}$ ，其中$\sigma$ 表示自环图中自环的个数。将图能量这一概念从简单图推广至自环图是十分有必要的，在化学图论中，杂原子常用自环来进行表示，表明它们有一个未配对的电子；在有机化学中，杂原子是指在有机化合物中，除了碳和氢以外的其他原子，最常见的杂原子例如氮原子、硫原子、氧原子，它们具备高度的反应性，而杂环化合物普遍存在于药物分子的结构之中。文献[11] [12]详细阐述了自环在分子中的作用。2024年，Liu等学者在文献[13]中通过图的最大度、最小度、谱距等参数构造出了许多自环图能量的上下界。受上述结果的启发，本文主要利用矩阵理论与已有不等式来研究自环图能量的新下界。

2. 预备知识

Gutman等学者在文献[10]中定义自环图$G_S$ 是在简单图$G$ 上对属于集合$S$ 中的顶点添加一个自环而得到的图，其中$S\subseteq V\left(G\right)$ ，$V\left(G\right)$ 为$G$ 的顶点集，$S$ 即为自环图$G_S$ 中带自环顶点的集合，且自环的个数记为$\left|S\right|=\sigma$ 。$G_S$ 的邻接矩阵$A\left(G_S\right)={\left[a_{ij}\right]}_{n\times n}$ 则定义为一个$n\times n$ 阶实对称矩阵且邻接矩阵的每个元素$a_{ij}$ 满足

$a_{ij}=\{\begin{array}{ll}1,\hfill & 若i\ne j且v_i和v_j相邻;\hfill \\ 0,\hfill & 若i\ne j且v_i和v_j不相邻;\hfill \\ 1,\hfill & 若i=j且v_i\in S;\hfill \\ 0,\hfill & 若i=j且v_i\notin S.\hfill \end{array}$

因此，自环图$G_S$ 邻接矩阵$A\left(G_S\right)$ 的特征值就记为自环图$G_S$ 的邻接特征值，简称$G_S$ 的邻接特征值。

自环图$G_S$ 的能量$E\left(G_S\right)$ 被Gutman等学者在文献[10]中定义为

$E(G_S)={\displaystyle \sum _{i=1}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|}$ ，

其中，${\lambda }_1,\dots ,{\lambda }_n$ 为$G_S$ 的邻接特征值，$\sigma$ 为自环图中自环的个数，$n$ 为自环图中顶点的个数。

引理1 [10] 设$G_S$ 为简单图上添加自环而得到的自环图，满足$S\subseteq V\left(G\right)$ 以及$\left|S\right|=\sigma$ 。若${\left\{{\lambda }_i\right\}}_{1\le i\le n}$ 为$G_S$ 邻接矩阵的特征值，则有

${\displaystyle \sum _{i=1}^n{\lambda }_i=\sigma ,}{\displaystyle \sum _{i=1}^n{\lambda }_i^2=2m+\sigma }$ ，

以及

${{\displaystyle \sum _{i=1}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|}}^2=2m+\sigma -\frac{{\sigma }^2}{n}$ 。

引理2 [14] 设$G_S$ 为简单图上添加自环而得到的自环图，满足$S\subseteq V\left(G\right)$ 以及$\left|S\right|=\sigma$ 。若${\left\{{\lambda }_i\right\}}_{1\le i\le n}$ 为$G_S$ 邻接矩阵的特征值，则有

${\displaystyle \sum _{i<j}\left|{\lambda }_i-\frac{\sigma }{n}\right|}\left|{\lambda }_j-\frac{\sigma }{n}\right|\ge m+\frac{\sigma \left(n-\sigma \right)}{2n}$ ，

并且等式取等当且仅当$G_S$ 为完全不连通图并且$\sigma =0$ 或$\sigma =n$ 。

定理3 [14] 设$G_S$ 为简单图上添加自环而得到的自S环图，满足$S\subseteq V\left(G\right)$ 以及$\left|S\right|=\sigma$ 。若${\left\{{\lambda }_i\right\}}_{1\le i\le n}$ 为$G_S$ 邻接矩阵的特征值，则有

$\frac{2m+\sigma }{n}\le {\lambda }_1\left(G_S\right)\le \sqrt{2m+\sigma }$ ，

并且当$G=K_n$ 并且$\sigma =n$ 时左右等式取等。

定理4 [15] (Ozeki’s inequality) 设$a=\left(a_1,\dots ,a_n\right)$ 以及$b=\left(b_1,\dots ,b_n\right)$ 为$n$ 元实数组，并满足$0\le m_1\le a_i\le M_1$ 以及$0\le m_2\le b_i\le M_2$ ，其中$m_1=\underset{i=1,\dots ,n}{\min }{a}_i$ ，$M_1=\underset{i=1,\dots ,n}{\max }{a}_i$ 以及$m_2=\underset{i=1,\dots ,n}{\min }{b}_i$ ，$M_2=\underset{i=1,\dots ,n}{\max }{b}_i$ 。则有

$\left({\displaystyle \sum _{i=1}^n{a}_i^2}\right)\left({\displaystyle \sum _{i=1}^n{b}_i^2}\right)-{\left({\displaystyle \sum _{i=1}^n{a}_i{b}_i}\right)}^2\le \frac{n^2}{3}{\left(M_1{M}_2-m_1{m}_2\right)}^2$ 。

3. 主要结果及其证明

本节主要通过利用上述引理和定理来得到自环图能量的新下界。注意到定理3中不等式右半部分可以加强为充要条件，下面我们给出自环图取得这个最大特征值上界时充要条件的详细证明。

定理5 设自环图$G_S$ 的点数为$n$ ，边数为$m$ ，自环个数为$\sigma$ ；${\left\{{\lambda }_i\right\}}_{1\le i\le n}$ 为$G_S$ 邻接矩阵的特征值，则有

${\lambda }_1\left(G_S\right)\le \sqrt{2m+\sigma }$ ，

其中，${\lambda }_1\left(G_S\right)$ 代表$G_S$ 的最大特征值，并且等式成立，即${\lambda }_1\left(G_S\right)=\sqrt{2m+\sigma }$ 当且仅当$G_S=\widehat{K_{\sigma }}\cup \left(n-\sigma \right)K_1$ ，其中$\widehat{K_{\sigma }}$ 代表完全图$K_{\sigma }$ 的所有顶点都加上自环；$K_1$ 代表孤立顶点。进一步，若$G_S$ 是连通的，则$G_S=\widehat{K_n}$ 。

证明 由${\displaystyle {\sum }_{i=1}^n{\lambda }_1^2=2m+\sigma }$ ，因此

${\lambda }_1^2\le {\displaystyle {\sum }_{i=1}^n{\lambda }_1^2=2m+\sigma }$ ，

并且等式成立当且仅当${\lambda }_1=\sqrt{2m+\sigma }$ 以及${\lambda }_i=0,i=2,\dots ,n$ 。因此，$G_S$ 的谱为

$Spec\left(G_S\right)=\left\{\sqrt{2m+\sigma },0,\dots ,0\right\}$ ，

其中，0为$n-1$ 重，$\sqrt{2m+\sigma }$ 为1重。

对于充分性，当$G_S=\widehat{K_{\sigma }}\cup \left(n-\sigma \right)K_1$ 时，由所有顶点都带自环的完全图与孤立顶点的特征值可知，$G_S$ 的谱为

$Spec\left(G_S\right)=\left\{\sigma ,0,\dots ,0\right\}$ ，

其中0为$n-1$ 重，$\sigma$ 为1重。此时$G_S=\widehat{K_{\sigma }}\cup \left(n-\sigma \right)K_1$ ，因此$G_S$ 的边数$m=\frac{\sigma \left(\sigma -1\right)}{2}$ ，代入$\sqrt{2m+\sigma }$ 则有$\sqrt{2m+\sigma }=\sigma$ ，充分性成立。

对于必要性，由于邻接矩阵$A\left(G_S\right)$ 为一个实对称矩阵，其代数重数等于其几何重数，再结合$G_S$ 的谱，可知邻接矩阵$A\left(G_S\right)$ 的秩一定为1。又由于$G_S$ 包含$\sigma$ 个自环，因此邻接矩阵$A\left(G_S\right)$ 的对角线上一定包含$\sigma$ 个1，由于邻接矩阵$A\left(G_S\right)$ 的秩一定为1，因此对角线上元素为1的那些行列构成一个$\sigma \times \sigma$ 阶的全一矩阵$J_{\sigma \times \sigma }$ ，存在置换矩阵$P$ 使得邻接矩阵$A\left(G_S\right)$ 经过置换后有如下形式：

$P^{T}A\left(G_S\right)P=\left[\begin{array}{ll}{J}_{\sigma \times \sigma }\hfill & O_{\sigma \times \left(n-\sigma \right)}\hfill \\ O_{\left(n-\sigma \right)\times \sigma }\hfill & O_{\left(n-\sigma \right)\times \left(n-\sigma \right)}\hfill \end{array}\right]$ ，

其中，$J_{\sigma \times \sigma }$ 为$\sigma \times \sigma$ 阶全一矩阵，$O$ 为零矩阵。

因此，邻接矩阵$A\left(G_S\right)$ 所对应的图即为$G_S=\widehat{K_{\sigma }}\cup \left(n-\sigma \right)K_1$ ，其中$\widehat{K_{\sigma }}$ 代表完全图$K_{\sigma }$ 的所有顶点都加上自环；$K_1$ 代表孤立顶点。若$G_S$ 是连通的，则说明$G_S$ 不包含孤立顶点，因此$G_S=\widehat{K_{\sigma }}$ 。

结合引理2和定理5，可以得到一个与${\lambda }_1,\sigma$ 和$n$ 相关的新下界。

定理6 设自环图$G_S$ 的点数为$n$ ，边数为$m$ ，自环个数为$\sigma$ ；${\left\{{\lambda }_i\right\}}_{1\le i\le n}$ 为$G_S$ 邻接矩阵的特征值，则有

$E\left(G_S\right)\ge \sqrt{2{\lambda }_1^2-\frac{2{\sigma }^2}{n}}$ ，

等式成立当且仅当$G_S=n{K}_1$ 或$G_S=\widehat{K_1}$ 。

证明 由引理2和定理5，则有

$E{\left(G_S\right)}^2={\left({\displaystyle \sum _{i=1}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|}\right)}^2={{\displaystyle \sum _{i=1}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|}}^2+2{\displaystyle \sum _{i<j}\left|{\lambda }_i-\frac{\sigma }{n}\right|\left|{\lambda }_j-\frac{\sigma }{n}\right|}$

$\begin{array}{c}\ge 2m+\sigma -\frac{{\sigma }^2}{n}+2m+\frac{\sigma \left(n-\sigma \right)}{n}\\ =4m+2\sigma -\frac{2{\sigma }^2}{n}\\ \ge 2{\lambda }_1^2-\frac{2{\sigma }^2}{n}.\end{array}$

由于等式在引理2和定理5取等的充要条件分别为$G_S=n{K}_1$ 或$G_S=n\widehat{K_1}$ 以及$G_S=\widehat{K_{\sigma }}\cup \left(n-\sigma \right)K_1$ 。因此，等式取等的充要条件为$G_S=n{K}_1$ 或$G_S=\widehat{K_1}$ 。

Cauchy-Schwarz不等式是一类经典的不等式，具备非常丰富的应用场景，McClelland就在文献[6]中通过Frobenius范数和柯西不等式对拉格朗日恒等式进行放缩，从而首次给出了简单图能量的上界$E\left(G\right)\le \sqrt{2mn}$ 。因此，一些形如Cauchy-Schwarz不等式的其他不等式也开始被国内外学者应用于图能量上下界的探究，其中Ozeki不等式就被Shetty和Bhat在文献[14]中用于证明自环图的first Zagreb index这一指标的上界。利用Ozeki不等式，通过先对$a_i$ 与$b_i$ 取特殊的、可以配凑出自环图能量定义的取值，再根据$a_i$ 与$b_i$ 的取值，得到$a_i$ 与$b_i$ 的最大值与最小值，即$M_1,M_2$ 与$m_1,m_2$ 的取值，也可以得到自环图能量的一个新下界。

定理7 设自环图$G_S$ 的点数为$n$ ，边数为$m$ ，自环个数为$\sigma$ ；${\left\{{\lambda }_i\right\}}_{1\le i\le n}$ 为$G_S$ 邻接矩阵的特征值且满足$\left|{\lambda }_1-\frac{\sigma }{n}\right|\ge \cdots \ge \left|{\lambda }_n-\frac{\sigma }{n}\right|$ 。则有

$E\left(G_S\right)\ge \sqrt{n\left(2m+\sigma -\frac{{\sigma }^2}{n}\right)-\frac{n^2}{3}{\left(\left|{\lambda }_1-\frac{\sigma }{n}\right|-\left|{\lambda }_n-\frac{\sigma }{n}\right|\right)}^2}$ 。

证明 设$a_i=\left|{\lambda }_i-\frac{\sigma }{n}\right|,b_i=1,i=1,\dots ,n$ 。

则有$m_1=\underset{i=1,\dots ,n}{\min }{a}_i=\left|{\lambda }_1-\frac{\sigma }{n}\right|,M_1=\underset{i=1,\dots ,n}{\max }{a}_i=\left|{\lambda }_n-\frac{\sigma }{n}\right|,m_2=\underset{i=1,\dots ,n}{\min }{b}_i=1,M_2=\underset{i=1,\dots ,n}{\max }{b}_i=1$ 将其代入定理4，则有

$n{{\displaystyle \sum _{i=1}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|}}^2-{\left({\displaystyle \sum _{i=1}^n\left|{\lambda }_i-\frac{\sigma }{n}\right|}\right)}^2\le \frac{n^2}{3}{\left(\left|{\lambda }_1-\frac{\sigma }{n}\right|-\left|{\lambda }_n-\frac{\sigma }{n}\right|\right)}^2$ ，

化简后即为

$E\left(G_S\right)\ge \sqrt{n\left(2m+\sigma -\frac{{\sigma }^2}{n}\right)-\frac{n^2}{3}{\left(\left|{\lambda }_1-\frac{\sigma }{n}\right|-\left|{\lambda }_n-\frac{\sigma }{n}\right|\right)}^2}$ 。

4. 总结

在本文中，我们先是利用每个顶点都带自环的完全图和孤立顶点的特征值及其边数给出了自环图最大特征值上界取等条件下的充分条件，再利用矩阵理论得到了取等条件下的必要条件，从而得到了这个自环图最大特征值上界取等时的充要条件。利用这个上界与另外一些与自环图特征值相关的已有结论，我们给出了一个与${\lambda }_1,\sigma$ 和$n$ 相关的自环图能量新下界并给出了等号取等时的充要条件；其次，我们发现了一个形如Cauchy-Schwarz不等式的不等式，即Ozeki不等式，可以被用于探究自环图能量的新下界。利用Ozeki不等式，通过先对$a_i$ 与$b_i$ 取可以配凑出自环图能量定义的取值，再根据$a_i$ 与$b_i$ 的取值，得到$M_1,M_2$ 与$m_1,m_2$ 的取值，我们也给出了自环图能量的一个新下界。