上海理工大学学报  2019, Vol. 41 Issue (4): 327-330 PDF

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 基本概念

${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|}$

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

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

 $\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}}}$

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)}$

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{。}}$

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

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

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}$ 中不可能同时有整数和非整有理数。

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

 $\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}$

 $\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)

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

 $\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)

${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}}$

 $\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)

 $\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)

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)

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

$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