上海理工大学学报  2019, Vol. 41 Issue (4): 327-330   PDF    
图的Seidel Laplacian-Estrada指标
孔祥瑀, 吴宝丰     
上海理工大学 理学院,上海 200093
摘要: 设G为简单图,di表示顶点vi的度,G的Seidel Laplacian矩阵SLG)是一个对角元为n−1−2di,非对角元为 ±1的实对称矩阵,当顶点vivj相邻时,(SLG) )ij=1,否则,(SLG) )ij=−1。引入并研究了Seidel Laplacian矩阵的Estrada指标,给出了该指标的上、下界,以及它与Seidel Laplacian能量之间的关系。
关键词: Seidel Laplacian矩阵     Seidel Laplacian-Estrada指标     Seidel Laplacian能量         
Seidel Laplacian-Estrada Index of Graphs
KONG Xiangyu, WU Baofeng     
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Let G be a simple graph and di be the degree of the vertex vi. The Seidel Laplacian matrix of a graph G is a real symmetric matrix with diagonal elements of n−1−2di and off-diagonal elements of ±1. If the vertices vi and vj are adjacent, (SL(G))ij=1, and otherwise, (SL(G))ij=−1. The Seidel Laplacian-Estrada index was introduced and investigated. The upper and lower bounds for the Seidel Laplacian-Estrada index, and the relationship between the Seidel Laplacian-Estrada index and the Seidel Laplacian energy are provided.
Key words: Seidel Laplacian matrix     Seidel Laplacian-Estrada index     Seidel Laplacian energy     bound    
1 基本概念

本文研究的图均为简单无向图,有 $m$ 条边、 $n$ 个顶点,记为 $G$ ,它的补图用 $\bar G$ 表示。图的Seidel矩阵 ${{S}}\left( G \right)$ 定义为 ${{J}} - {{I}} - 2{{A}}(G)$ (见文献[1]),其中, ${{J}}$ 为全1矩阵, ${{I}}$ 为单位矩阵, ${{A}}(G)$ 为图 $G$ 的邻接矩阵,易知 ${{S}}(G) = {{A}}(\bar G) - {{A}}(G)$ 。设 ${\lambda _1},{\lambda _2}, \cdots ,{\lambda _n}$ 表示Seidel矩阵的特征值,则图 $G$ 的Seidel能量定义为 ${E_S}\left( G \right) = \displaystyle\sum\limits_{i = 1}^n {\left| {{\lambda _i}} \right|} $ ,Seidel-Estrada指标定义为 $ SEE\left( G \right) = $ $\displaystyle\sum\limits_{i = 1}^n {{{\rm{e}}^{{\lambda _i}}}} $ (见文献[2])。

${d_i}$ 表示顶点 ${v_i}$ 的度,文献[3]给出了图 $G$ 的Seidel Laplacian矩阵的定义,即 ${{{S}}_L}\left( G \right) = {{{D}}_S}\left( G \right) - $ ${{S}}\left( G \right)$ ,其中, ${{{D}}_S}\left( G \right) = {\rm{diag}} (n - 1 - 2{d_1},n - 1 - 2{d_2}, \cdots , $ $n - 1 - 2{d)_n}$ 。Seidel Laplacian矩阵是一个对角元为 $n - 1 - 2{d_i}$ ,非对角元为±1的实对称矩阵,当顶点 ${v_i}$ ${v_j}$ 相邻时, ${\left( {{{{S}}_L}(G)} \right)_{ij}} = 1$ ,否则, ${\left( {{{{S}}_L}(G)} \right)_{ij}} = - 1$ 。由于 ${{{S}}_L}(G)$ 的行和均为0,所以,它必有特征值0。 ${{{S}}_L}(G)$ 的谱,即它的所有特征值构成的多重集合,称为图 $G$ 的Seidel Laplacian谱,如完全图Kn的Seidel Laplacian谱为 $\{ 0,{( - n)^{(n - 1)}}\} $ ,完全二部图 ${K_{p,q}}$ 的Seidel Laplacian谱为 $\{ {(p - q)^{(p - 1)}},{(q - p)^{(q - 1)}},0,$ $ - (p + q)\} $ 。易知 ${{{S}}_L}(\bar G) = - {{{S}}_L}(G)$ ,所以,补图的Seidel Laplacian谱完全由原图的谱确定。设 ${{D}}(G) = $ ${\rm{diag}}({d_1},{d_2}, \cdots ,{d_n})$ 为度对角矩阵,注意到 ${{{D}}_S}\left( G \right) = $ ${{D}}\left( {\bar G } \right) - {{D}}\left( G \right)$ ,于是, ${{{S}}_L}\left( G \right) = {{L}}\left( {\bar G } \right) - {{L}}\left( G \right)$ ,其中, ${{L}}(G) = {{D}}(G) - {{A}}(G)$ 表示图 $G$ 的Laplacian矩阵。

$G$ 的Laplacian能量定义为 ${E_L}\left( G \right) = \displaystyle\sum\limits_{i = 1}^n {\left| {{\mu _i} - \dfrac{{2m}}{n}} \right|} $ ,其中, ${\mu _i}$ ${ L}(G)$ 的特征值。类似地,图 $G$ 的 Seidel Laplacian 能量定义为[3]

${E_{SL}}\left( G \right) = \sum\limits_{i = 1}^n {\left| {{\sigma _i} - \frac{{n\left( {n - 1} \right) - 4m}}{n}} \right|} $

其中, ${\sigma _1},{\sigma _2},\cdots,{\sigma _n}$ ${{{S}}_L}\left( G \right)$ 的特征值。令 ${\xi _i} ={\sigma _i} - $ $ \dfrac{{n\left( {n -1} \right) -4m}}{n}$ ( $i = 1,2, \cdots ,n$ ),则 $\displaystyle\sum\limits_{i = 1}^n {{\xi _i}} = 0$ ,于是,图 $G$ 的Seidel Laplacian能量可以表示为

${E_{SL}} = {E_{SL}}\left( G \right) = \sum\limits_{i = 1}^n {\left| {{\xi _i}} \right|}$

图的Estrada指标有若干种,见文献[4-7]以及它们的参考文献。类似Seidel-Estrada指标,本文引入图的Seidel Laplacian-Estrada指标,定义为

$SLEE = SLEE\left( G \right) = \sum\limits_{i = 1}^n {{{\rm{e}}^{{\xi _i}}}}$

现研究图的Seidel Laplacian-Estrada指标,给出该指标的上、下界以及它与Seidel Laplacian能量之间的关系。

2 Seidel Laplacian-Estrada指标的上下界

为方便起见,设 ${\xi _1} \geqslant{\xi _2} \geqslant \cdots \geqslant {\xi _n}$ ,令 ${S_k}\left( G \right) = $ $\displaystyle\sum\limits_{i = 1}^n {\xi _i^k} $ ${S^k}\left( G \right) = \displaystyle\sum\limits_{i = 1}^n {{{\left| {{\xi _i}} \right|}^k}} $ ,其中, ${S_0}(G) = {S^0}(G) = n$ ${S_1}(G) = 0$ ${S^1}(G) = {E_{SL}}(G)$ 。令 ${Z_1}\left( G \right) = \displaystyle\sum\limits_{i = 1}^n {d_i^2} $ ,称为图 $G$ 的第一Zagreb指标,它的数学性质在文献[8-9]中有研究。

引理1[3]  设 $G$ $m$ 边的 $n$ 阶图,则 ${S^2}\left( G \right) = $ ${S_2}\left( G \right) = \displaystyle\sum\limits_{i = 1}^n {\xi _i^2} = M$ ,其中, $M = n\left( {n - 1} \right) + 4{Z_1}\left( G \right) -$ $ \dfrac{{16\;{m^2}}}{n}$

引理2 (Hölder不等式[10]  设 $p,q > 1$ , $\dfrac{1}{p} + \dfrac{1}{q} = $ $1 $ , 则对于任意 ${{X}} \!=\! {\left( {{x_1},{x_2},\cdots,{x_n}} \right)^{\rm{T}}}$ ${{Y}} \!=\! {\left( {{y_1},{y_2},\cdots,{y_n}} \right)^{\rm{T}}}\in $ $ {\mathbb{R}^n} $ ,有

$\left|{ \sum\limits_{k = 1}^n {x_k}{y_k} }\right| \leqslant {\left( {\sum\limits_{k = 1}^n {{{\left| {{x_k}} \right|}^p}} } \right)^{\frac{1}{p}}}{\left( {\sum\limits_{k = 1}^n {{{\left| {{y_k}} \right|}^q}} } \right)^{\frac{1}{q}}}$

定理1  设 $k > 2$ ,则 ${S^k}\left( G \right) = \displaystyle\sum\limits_{i = 1}^n {{{\left| {{\xi _i}} \right|}^k}} \geqslant {M^{\frac{k}{2}}}{n^{1 - \;\frac{k}{2}}}$

证明  令 ${{X }}= {\left( {\xi _1^2,\xi _2^2, \cdots ,\xi _n^2} \right)^{\rm{T}}}$ ${{Y}} = {\left( {1,1, \cdots ,1} \right)^{\rm{T}}}$ ,由Hölder不等式 $\left| {{{{X}}^{\rm{T}}}{{Y}}} \right| \leqslant {\left\| {{X}} \right\|_p}{\left\| {{Y}} \right\|_q}$ (其中, $p,q > 1$ , $\dfrac{1}{p} + \dfrac{1}{q} = 1$ ),可得 $\displaystyle\sum\limits_{i = 1}^n {\xi _i^2} \leqslant {\left( {\displaystyle\sum\limits_{i = 1}^n {{{\left| {\xi _i^2} \right|}^p}} } \right)^{\frac{1}{p}}}{\left( {\displaystyle\sum\limits_{i = 1}^n {{1^q}} } \right)^{\frac{1}{q}}}$ 。因为, $\displaystyle\sum\limits_{i = 1}^n {\xi _i^2} = M$ ,所以, ${\left( {\displaystyle\sum\limits_{i = 1}^n {{{\left| {{\xi _i}} \right|}^{2p}}} } \right)^{\frac{1}{p}}} \geqslant \dfrac{M}{{{n^{1 - \;\frac{1}{p}}}}}$ $ \displaystyle\sum\limits_{i = 1}^n {{{\left| {{\xi _i}} \right|}^{2p}}} \geqslant $ ${M^p}{n^{1 - p}}$ 。令 $2p = k$ ,此时满足 $p > 1$ ,从而有 ${S^k}\left( G \right) = $ $ \displaystyle\sum\limits_{i = 1}^n {{{\left| {{\xi _i}} \right|}^k}} \geqslant {M^{\frac{k}{2}}}{n^{1 - \;\frac{k}{2}}}$

引理3  设Gm边的n阶图,则

a. $SLEE\left( G \right) = \displaystyle\sum\limits_{k = 0}^\infty {\dfrac{{{S_k}\left( G \right)}}{{k!}}}$

b. $SLEE\left( G \right) = n + \displaystyle\sum\limits_{k = 2}^\infty {\left( {\dfrac{1}{{k!}}\displaystyle\sum\limits_{i = 1}^n {\xi _i^k} } \right)}$

证明   a. $SLEE\left( G \right)\;\; =\;\;\displaystyle\sum\limits_{i = 1}^n {{{\rm{e}}^{{\xi _i}}}} \;\; =\; \;\displaystyle\sum\limits_{i = 1}^n {\displaystyle\sum\limits_{k = 0}^\infty {\frac{{\xi _i^k}}{{k!}}} } \;=\; $ $\displaystyle\sum\limits_{k = 0}^\infty {\left( {\frac{1}{{k!}}\displaystyle\sum\limits_{i = 1}^n {\xi _i^k} } \right)} = \displaystyle\sum\limits_{k = 0}^\infty {\frac{{{S_k}\left( G \right)}}{{k!}}} $

b. $SLEE\left( G \right) \;\;= \;\displaystyle\sum\limits_{k = 0}^\infty {\frac{{{S_k}\left( G \right)}}{{k!}}} \;\;=\; {S_0}\left( G \right) \;\;+ \;{S_1}\left( G \right)\; + $ $\displaystyle\sum\limits_{k = 2}^\infty {\dfrac{{{S_k}\left( G \right)}}{{k!}}} = n + \displaystyle\sum\limits_{k = 2}^\infty {\left( {\dfrac{1}{{k!}}\displaystyle\sum\limits_{i = 1}^n {\xi _i^k} } \right)}$ ${\text{。}} $

引理4Gm边的n阶图,n≥2,则

a. 不可能有 ${\xi _1} = {\xi _2} = \cdots = {\xi _n}$

b. ${\xi _1},{\xi _2}, \cdots ,{\xi _n}$ 中不可能同时有整数和非整有理数。

证明   a. 假设 ${\xi _1} = {\xi _2} = \cdots = {\xi _n}$ ,根据 $\displaystyle\sum\limits_{i = 1}^n {{\xi _i}} = 0$ ,可得 ${\xi _i} = 0$ ( $i = 1,2, \cdots ,n$ ),从而有 ${\sigma _i} = \dfrac{{n\left( {n - 1} \right) - 4m}}{n}$ ,记为 $\sigma $ 。由于 ${{{S}}_L}\left( G \right)$ 是实对称矩阵,故存在可逆矩阵 ${{P}}$ ,使得 ${{{P}}^{ - 1}}{{{S}}_L}\left( G \right){{P}} = {\rm{diag}}\left( {{\sigma _1},{\sigma _2},\cdots,{\sigma _n}} \right) = \sigma {{I}}$ 。于是, ${{{S}}_L}\left( G \right) = {{P}}\left( {\sigma {{I}}} \right){{{P}}^{ - 1}} = \sigma {{I}}$ ,从而有 ${{ S}_L}\left( G \right)$ 的非对角元全为0,与 ${{{S}}_L}\left( G \right)$ 的定义矛盾。

b. 由于 ${{{S}}_L}(G)$ 的特征多项式是首系数为1的整系数多项式,故其特征值 ${\sigma _1},{\sigma _2},\cdots,{\sigma _n}$ 均为代数整数(即整数或无理数)。又 ${\xi _i} = {\sigma _i} - \dfrac{{n\left( {n - 1} \right) - 4\;m}}{n}$ ( $ i = 1,$ $2, \cdots ,n$ ),于是,当 $\dfrac{{4\;m}}{n}$ 为整数时, ${\xi _1},{\xi _2}, \cdots ,{\xi _n}$ 为整数或无理数;当 $\dfrac{{4\;m}}{n}$ 为非整有理数时, ${\xi _1},{\xi _2}, \cdots ,{\xi _n}$ 则为无理数或非整有理数。因此, ${\xi _1},{\xi _2}, \cdots ,{\xi _n}$ 中不可能同时有整数和非整有理数。

引理5  设 $G$ $m$ 边的 $n$ 阶图, $n \geqslant 2$ ,则有:a. ${\xi _1} > 0$ ;b. ${\xi _n} < 0$

证明  根据 ${\xi _1} \geqslant{\xi _2} \geqslant \cdots \geqslant {\xi _n}$ $\displaystyle\sum\limits_{i = 1}^n {{\xi _i}} = 0$ ,可知 ${\xi _1} \geqslant 0,{\xi _n} \leqslant 0$ 。假设 ${\xi _1} = 0$ ,则 ${\xi _1} = {\xi _2} = \cdots = {\xi _n} = 0$ ,与引理4的a矛盾,所以, ${\xi _1} > 0$ 。类似地, ${\xi _n} < 0$

现考虑Seidel Laplacian-Estrada指标的界,根据算术−几何平均值不等式, $SLEE(G) \!\geqslant\! n\sqrt[n]{{{{\rm{e}}^{{\xi _1} \!+\! {\xi _2} \!+\!\cdots \!+\! {\xi _n}}}}}\! = \! $ $n$ ,当 $n \geqslant 2$ 时,由引理4的a可知等号不成立,所以, $SLEE > n$ 。下面的定理2改进了该下界,其证明思想来源于文献[2]。

定理2  设Gm边的n阶图,n≥2,则

$SLEE\left( G \right) > \sqrt {{n^2} + 2M} $

证明  当 $n = 2,3$ 时,图 $G$ 只有6种情形,它们的Seidel Laplacian-Estrada指标和 $\sqrt{n^2+2\;m} $ 可以直接计算并作比较,如表1所示,显然,当 $n = 2,3$ 时结论成立。


表 1 图的Seidel Laplacian-Estrada指标和下界 Table 1 Seidel Laplacian-Estrada index and lower bound of a graph

考虑 $n \geqslant 4$ 情形。由于

$\quad SLE{E^2}\left( G \right) = {\left( {\sum\limits_{i = 1}^n {{{\rm{e}}^{{\xi _i}}}} } \right)^2} = \sum\limits_{i = 1}^n {{{\rm{e}}^{2{\xi _i}}}} + 2\sum\limits_{i < j} {{{\rm{e}}^{{\xi _i}}}} {{\rm{e}}^{{\xi _j}}}$ (1)

根据算术−几何平均值不等式,有

$\begin{split}&\quad 2\sum\limits_{i < j} {{{\rm{e}}^{{\xi _i}}}{{\rm{e}}^{{\xi _j}}}} \geqslant n\left( {n - 1} \right){\left( {\prod\limits_{i < j} {{{\rm{e}}^{{\xi _i}}}{{\rm{e}}^{{\xi _j}}}} } \right)^{\frac{2}{{n\left( {n - 1} \right)}}}} =\qquad\qquad\qquad\qquad\qquad\qquad\\ & \qquad n\left( {n - 1} \right){\left[ {{{\left( {\prod\limits_{i = 1}^n {{{\rm{e}}^{{\xi _i}}}} } \right)}^{n - 1}}} \right]^{^{\frac{2}{{n\left( {n - 1} \right)}}}}} =\\ &\qquad n\left( {n - 1} \right){\left( {{{\rm{e}}^{{S_1}\left( G \right)}}} \right)^{\frac{2}{n}}} = n\left( {n - 1} \right) \\[-15pt] \end{split} $ (2)

另外,

$\begin{split} &\quad \sum\limits_{i = 1}^n {{{\rm{e}}^{2{\xi _i}}}} = \sum\limits_{i = 1}^n {\sum\limits_{k = 0}^\infty {\frac{{{{\left( {2{\xi _i}} \right)}^k}}}{{k!}}} } =\sum\limits_{i = 1}^n {\frac{{{{\left( {2{\xi _i}} \right)}^0}}}{{0!}}} + \sum\limits_{i = 1}^n {\frac{{{{\left( {2{\xi _i}} \right)}^1}}}{{1!}}} + \qquad\qquad\\ & \qquad\sum\limits_{i = 1}^n {\frac{{{{\left( {2{\xi _i}} \right)}^2}}}{{2!}}} + \sum\limits_{i = 1}^n {\sum\limits_{k \geqslant 3} {\frac{{{{\left( {2{\xi _i}} \right)}^k}}}{{k!}}} } =\\ & \qquad n + 2{S_1} + 2{S_2} + \sum\limits_{i = 1}^n {\sum\limits_{k \geqslant 3} {\frac{{{{\left( {2{\xi _i}} \right)}^k}}}{{k!}}} } =\\ &\qquad n + 2M + \sum\limits_{i = 1}^n {\sum\limits_{k \geqslant 3} {\frac{{{{\left( {2{\xi _i}} \right)}^k}}}{{k!}}} } \end{split} $

由于 $\displaystyle\sum\limits_{k \geqslant 3} {\dfrac{{{{\left( {2{\xi _i}} \right)}^k}}}{{k!}}} \geqslant 8\displaystyle\sum\limits_{k \geqslant 3} {\dfrac{{\xi _i^k}}{{k!}}} $ ,则取 $\gamma \in \left[ {0,8} \right]$ 时,有

$\begin{split}&\quad \sum\limits_{i = 1}^n {{{\rm{e}}^{2{\xi _i}}}} \geqslant n + 2M + \gamma \sum\limits_{i = 1}^n {\sum\limits_{k \geqslant 3} {\frac{{\xi _i^k}}{{k!}}} } =\qquad\qquad\qquad\qquad\qquad \\ & \qquad n + 2M - \gamma n - \frac{1}{2}\gamma M + \gamma \sum\limits_{i = 1}^n {\sum\limits_{k = 0}^\infty {\frac{{\xi _i^k}}{{k!}}} } =\\ & \qquad n + 2M - \gamma n - \frac{1}{2}\gamma M + \gamma SLEE\left( G \right)\\[-15pt] \end{split} $ (3)

将式(2)和式(3)代入式(1),可得

$SLEE\left( G \right) \geqslant \frac{1}{2}\left( {\gamma + \sqrt {{{\left( {2n - \gamma } \right)}^2} + 2M\left( {4 - \gamma } \right)} } \right)$ (4)

考虑函数 $f\left( x \right) = x + \sqrt {{{\left( {2n - x} \right)}^2} + 2M\left( {4 - x} \right)} $ ,有 $f'(x) = 1 - \dfrac{{M + 2n - x}}{{\sqrt {{{(2n - x)}^2} + 2M(4 - x)} }}$ 。当 $n \geqslant 4,\;0 \leqslant x \leqslant 8$ 时, $f'(x) \leqslant 0$ 等价于 $M(M + 4n - 8) \geqslant 0$ ,而后者恒成立,故 $f\left( x \right)$ 单调递减。所以,可以在式(4)中取 $\gamma $ =0,可得 $SLEE\left( G \right) \geqslant \sqrt {{n^2} + 2M} $ 。若上式等号成立,则由式(2)可知, ${{\rm{e}}^{{\xi _i} + {\xi _j}}} = {{\rm{e}}^{{\xi _k}}}^{ + {\xi _l}}, \quad i,j,k,l \in$ $ \left\{ {1,2, \cdots ,\left. n \right\}} \right.$ ,从而有 ${\xi _1} = {\xi _2} =\cdots = {\xi _n}$ ,与引理4的a矛盾,所以,等号不成立。

定理3  设Gm边的n阶图,n≥2,则 $SLEE\left( G \right) < n - 1 - \sqrt M + {{\rm{e}}^{\sqrt M }}$

证明  根据引理3的b,有

$\begin{split} &\quad SLEE\left( G \right) = n + \sum\limits_{k = 2}^\infty {\left( {\frac{1}{{k!}}\sum\limits_{i = 1}^n {\xi _i^k} } \right)} \leqslant\qquad\qquad\qquad\qquad \\ &\qquad n + \sum\limits_{k = 2}^\infty {\left( {\frac{1}{{k!}}\sum\limits_{i = 1}^n {{{\left| {{\xi _i}} \right|}^k}} } \right)} = n + \sum\limits_{k = 2}^\infty {\left( {\frac{1}{{k!}}\sum\limits_{i = 1}^n {{{\left( {\xi _i^2} \right)}^{\frac{k}{2}}}} } \right)} \leqslant \\ & \qquad n + \sum\limits_{k = 2}^\infty {\frac{1}{{k!}}} {\left( {\sum\limits_{i = 1}^n {\xi _i^2} } \right)^{\frac{k}{2}}} = n - 1 - \sqrt M + {{\rm{e}}^{\sqrt M }}\\[-20pt] \end{split} $ (5)

若式(5)等号成立,则 ${\xi _n} = \left| {{\xi _n}} \right| \geqslant 0$ ,与引理5的b矛盾,所以,等号不成立。

3 Seidel Laplacian-Estrada指标与Seidel Laplacian能量之间的关系

${n_ + }$ 表示 ${\xi _i}(i = 1,2, \cdots ,n)$ 中正数的个数,当 $n \geqslant 2$ 时,由引理5的a可知, ${n_ + }\geqslant 1$ 。因为 $\displaystyle\sum\limits_{i = 1}^n {{\xi _i}} = 0$ ,所以

${E_{SL}} = {E_{SL}}\left( G \right) = 2\sum\limits_{i = 1}^{{n_ + }} {{\xi _i}} = - 2\sum\limits_{i = {n_ + } + 1}^n {{\xi _i}} $

定理4  设Gm边的n阶图,n $\geqslant $ 2,则

$ \begin{split} &\quad \frac{{\rm{e}}}{2}{E_{SL}}\left( G \right) + \left( {n - {n_ + }} \right){{\rm{e}}^{ - \;\frac{{{E_{SL}}\left( G \right)}}{{2\left( {n - {n_ + }} \right)}}}} \leqslant SLEE\left( G \right) < \qquad\qquad\\ & \qquad n - 1 - {E_{SL}}\left( G \right) + {{\rm{e}}^{{E_{SL}}\left( G \right)}} \\[-10pt] \end{split}$ (6)

式(6)左边等号成立当且仅当 ${\xi _1} = \cdots = {\xi _{{n_ + }}} = 1$ ${\xi _{{n_ + } + 1}} = \cdots = {\xi _n}$ 。特别地,当 $G \cong {K_{n/2,n/2}}$ $n$ 为偶数)时,式(6)左边等号成立。

证明 a. 先证下界。

因为, ${{\rm{e}}^x} \geqslant {\rm{e}}x$ 当且仅当 $x = 1$ 时等号成立,所以

$\sum\limits_{{\xi _i} > 0} {{{\rm{e}}^{{\xi _i}}}} = \sum\limits_{i = 1}^{{n_ + }} {{{\rm{e}}^{{\xi _i}}}} \geqslant \sum\limits_{i = 1}^{{n_ + }} {{\rm{e}}{\xi _i}} = \frac{{\rm{e}}}{2}{E_{SL}}$

又因为

$\begin{split} &\quad \sum\limits_{{\xi _i} \leqslant 0} {{{\rm{e}}^{{\xi _i}}}} = \sum\limits_{i = {n_ + } + 1}^n {{{\rm{e}}^{{\xi _i}}}} \geqslant \left( {n - {n_ + }} \right){\left( {\prod\limits_{i = {n_ + } + 1}^n {{{\rm{e}}^{{\xi _i}}}} } \right)^{\frac{1}{{n - {n_ + }}}}}=\qquad\qquad\qquad\qquad\qquad \\ & \qquad \left( {n - {n_ + }} \right){\left( {{{\rm{e}}^{\sum\limits_{i = {n_ + } + 1}^n {{\xi _i}} }}} \right)^{\frac{1}{{n - {n_ + }}}}} = \left( {n - {n_ + }} \right){{\rm{e}}^{ - \;\frac{{{E_S}_L}}{{2\left( {n - {n_ + }} \right)}}}} \end{split} $

所以

$\begin{split} &\quad SLEE\left( G \right) = \sum\limits_{{\xi _i} > 0} {{{\rm{e}}^{{\xi _i}}}} + {\sum\limits_{{\xi _i} \leqslant 0} {\rm{e}} ^{{\xi _i}}} \geqslant \qquad\qquad\qquad\qquad\qquad\qquad\\ & \qquad \frac{{\rm{e}}}{2}{E_{SL}} + \left( {n - {n_ + }} \right){{\rm{e}}^{ - \;\frac{{{E_{SL}}}}{{2\left( {n - {n_ + }} \right)}}}}\\[-15pt] \end{split} $ (7)

显然,式(7)等号成立当且仅当 ${\xi _1} = \cdots = $ $ {\xi _{{n_ + }}} = 1$ ${\xi _{{n_ + } + 1}} = \cdots = {\xi _n}$ 。特别地,当 $G \cong {K_{n/2,n/2}}$ 时,此时 $n$ 必为偶数,易得 ${{ {S}}_L}{({K_{n/2,n/2}})}$ 的谱为 $\{ {0^{(n - 1)}}, - n\} $ 。又 $\dfrac{{n\left( {n - 1} \right) - 4\,m}}{n} \!= \!- 1$ ,故 ${\xi _1} = \cdots =\,$ $ {\xi _{n - 1}} \!=\! 1$ ${\xi _n} = 1 - n$ ,式(7)等号成立。

b. 再证上界。

$\begin{split} &\quad SLEE\left( G \right) = n + \sum\limits_{k = 2}^\infty {\left( {\frac{1}{{k!}}\sum\limits_{i = 1}^n {\xi _i^k} } \right)} \leqslant n + \sum\limits_{k = 2}^\infty {\left( {\frac{1}{{k!}}\sum\limits_{i = 1}^n {{{\left| {{\xi _i}} \right|}^k}} } \right)} \leqslant \\ &\qquad n + \sum\limits_{k = 2}^\infty {\frac{1}{{k!}}} {\left( {\sum\limits_{i = 1}^n {\left| {{\xi _i}} \right|} } \right)^k} \!=\! n \!-\! 1 \!-\! {E_{SL}} \!+\! \sum\limits_{k = 0}^\infty {\frac{{E_{SL}^k}}{{k!}}} \!= \\ &\qquad n - 1 - {E_{SL}} + {{\rm{e}}^{{E_S}_L}}\\[-12pt] \end{split} $ (8)

若式(8)等号成立,则 ${\xi _n} = \left| {{\xi _n}} \right| \geqslant 0$ ,与引理5的b矛盾,所以,式(8)等号不成立。证毕。

若定理4中的式(6)左边不等式等号成立,则有:a. $\dfrac{{{n_ + }}}{{n - {n_ + }}}$ 为整数;b. $\dfrac{{4\;m}}{n}$ 为整数;c. SL(G)不同特征值只有2个:0和某非零整数。易知 ${\xi _{{n_ + } + 1}} =\cdots=$ $ {\xi _n} = - \dfrac{{{n_ + }}}{{n - {n_ + }}}$ 。根据引理4的b可知, $\dfrac{{{n_ + }}}{{n - {n_ + }}}$ 必须为整数。此时,图G的Seidel Laplacian谱为

$\left\{ {{{\left(n - \frac{{4\;m}}{n}\right)}^{({n_ + })}},\;{{\left(n - 1 - \frac{{4\;m}}{n} - \frac{n}{{n - {n_ + }}}\right)}^{(n - {n_ + })}}} \right\}$

考虑到 ${{{S}}_L}(G)$ 的特征值为代数整数,所以 $\dfrac{{4\;m}}{n}$ 为整数。又因为 ${{{S}}_L}(G)$ 必有特征值0,所以 ${{{S}}_L}(G)$ 的不同特征值只有2个:0和某非零整数。

$G$ 为平凡图时, $n = 1$ $SLEE(G) = 1$ ,易验证,定理2~4中的所有上、下界都能取到等号.

参考文献
[1]
VAN LINT J H, SEIDEL J J. Equilateral point sets in elliptic geometry[J]. Indagationes Mathematicae (Proceedings), 1966, 28(3): 335-348.
[2]
ASKARI J, IRANMANESH A, DAS K C. Seidel-Estrada index[J]. Journal of Inequalities and Applications, 2016, 2016: 120.
[3]
RAMANE H S, JUMMANNAVER R B, GUTMAN I. Seidel Laplacian energy of graphs[J]. International Journal of Applied Graph Theory, 2017, 1(2): 74-82.
[4]
DE LA PEÑA J A, GUTMAN I, RADA J. Estimating the Estrada index[J]. Linear Algebra and Its Applications, 2007, 427(1): 70-76.
[5]
CHEN X, HOU Y P. Some results on Laplacian Estrada index of graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2015, 73(1): 149-162.
[6]
DAS K C, LEE S G. On the Estrada index conjecture[J]. Linear Algebra and Its Applications, 2009, 431(1): 1351-1359.
[7]
ZHU B X. On the Laplacian Estrada index of graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2011, 66(2): 769-776.
[8]
GUTMAN I, DAS K C. The first Zagreb index 30 years after[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2004, 50(50): 83-92.
[9]
BOROVIĆANIN B, DAS K C, FURTULA B, et al. Bounds for Zagreb indices[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2017, 78(1): 17-100.
[10]
FINNER H. Some new inequalities for the range distribution, with application to the determination of optimum significance levels of multiple range tests[J]. Journal of the American Statistical Association, 1990, 85(409): 191-194. DOI:10.1080/01621459.1990.10475325