上海理工大学学报  2020, Vol. 42 Issue (4): 317-319, 367 PDF

Lower bounds of graph energy in terms of star matching number
WANG Mengmeng, HE Changxiang
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: The relationship between the energy $\varepsilon \left( G \right)$ and the ${K_{1,s}}$ -matching number ${\mu _s}\left( G \right)$ of a graph $G$ was focused. It is proved that $\varepsilon \left( G \right)$ $2\sqrt s {\mu _s}\left( G \right)$ . Furthermore, if each subgraph of $G$ satisfies some special conditions, then $\varepsilon \left( G \right)$ $2\sqrt s {\mu _s}\left( G \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( G \right)$ , where ${c_1}\left( G \right)$ is the number of odd cycles in $G$ . In addition, if the maximum degree of the tree $T$ is no more than 3, then $\varepsilon \left( T \right)$ $\left( {s + 1} \right){\mu _s}\left( T \right) - 1$ .
Key words: graph     energy     K1,s-matching
1 问题的提出

$G$ 是一个简单图，即没有环和重边的图， $V\left( G \right) = \left\{ {{v_1},{v_2}, \cdots ,{v_n}} \right\}$ $E\left( G \right)$ 分别表示 $G$ 的顶点集和边集，并且令A $\left( G \right) = {\left( {{a_{ij}}} \right)_{n \times n}}$ 表示 $G$ 的邻接矩阵。其中，若 ${v_i}{v_j} \in E\left( G \right)$ , ${a_{ij}} = 1$ ；否则， ${a_{ij}} = {\rm{0}}$ 。对于 $V\left( G \right)$ 的任一子集 $U$ ，以 $G - U$ 表示删除 $U$ 中的顶点以及与之相关联的所有边而得到的图。若 $H$ $G$ 的诱导子图，将用 $G - H$ 来表示诱导子图 $G - V\left( H \right)$ G的子图GH也称为HG中的补图，记为 $\overline H$ 。若 $x \in V \left( {G - H} \right)$ ，以 $H + x$ 表示 $G$ $V\left( H \right)$ $\left\{ x \right\}$ 的诱导子图。若 ${E_0}$ $E\left( G \right)$ 的子集，则 $G - {E_0}$ 表示在 $G$ 中去掉 ${E_0}$ 中所有边得到的子图。若 $G - {E_0}$ 不连通，则称 ${E_0}$ $G$ 的割集。

$G$ 的能量 $\varepsilon \left( G \right)$ 定义为 $G$ 的邻接矩阵A $\left( G \right)$ 的所有特征值的绝对值之和。除了文献[2]中得到的关于匹配数的图能量下界，还有以下常见的结论：

a. 文献[3]证明了恰有 $m$ 条边的所有图 $G$ 的能量 $\varepsilon \left( G \right)$ $2\sqrt m$ ，文献[4]将这个结果拓展到有向图 $D$ ，证明了有向图 $D$ 的能量 $\varepsilon \left( D \right)$ $\sqrt {{\rm{2}}{c_2}}$ ，其中， ${c_{\rm{2}}}$ $D$ 中长度为2的闭途径的个数。

b. 文献[5]证明了：若 $G$ 是具有 $m$ 条边的二分图，设 $\pm {\mu _{\rm{1}}},\cdots, \pm {\mu _N}$ $G$ 的特征值，令 ${M_k} = 2\displaystyle\sum\limits_{i = 1}^N {\mu _i^k}$ ，若 $q = \dfrac{{{M_4}}}{2}$ ，则 $\varepsilon \left( G \right)$ $2m\sqrt {\dfrac{m}{q}}$ ，即 $q$ 是4阶谱矩的一半时此式成立。

c. 文献[6]证明了：若 $G$ 不含长为4的圈作为诱导子图，则 $\varepsilon \left( G \right)$ $2\dfrac{{\sqrt {2\delta \varDelta } }}{{2\left( {\delta + \varDelta } \right) - 1}}\sqrt {2mn}$ , 其中， $n$ $G$ 的顶点数， $m$ $G$ 的边数， $\delta$ $\varDelta$ 分别为 $G$ 的最小度和最大度。

d. 文献[7]证明了：若 $G$ 为至少有一条边的图，设 $r$ , $s$ , $t$ 为任意偶数，若 $4r = s + t + 2$ ，则

 $\varepsilon \left( G \right)\geqslant \frac{{M_r^2\left( G \right)}}{{\sqrt {{M_s}\left( G \right){M_t}\left( G \right)} }}$ (1)

2 关于 ${K_{1,s}}$ −匹配数的图能量下界

$S \subseteq V\left( G \right)$ , $\overline S$ $S$ $V\left( G \right)$ 中的补集，以[ $S,\overline S$ ]表示一端在 $S$ 中、另一端在 $\overline S$ 中的所有边构成的集合。文献[8]中得到了关于图能量的2个结论，为引理1和引理2。

$M\left( G \right)$ $G$ 的一个最大 ${K_{1,s}}$ −匹配，由于 $M\left( G \right)$ $\cap$ $E\left( {{G_1}} \right)$ 至多覆盖 ${G_1}$ 中的所有点，所以，对于 $M\left( G \right)$ $\cap$ $E\left( {{G_1}} \right)$ ${K_{1,s}}$ −匹配的个数（记为 $s( M\left( G \right) \cap E\left( {{G_1}} \right) )$ ），有 $s\left( {M\left( G \right) \cap E\left( {{G_1}} \right)} \right)$ ${\mu _s}\left( {{G_1}} \right)$ 。类似地，有 $s\left( {M\left( G \right) \cap E\left( {{G_2}} \right)} \right)$ ${\mu _s}\left( {{G_2}} \right)$

${E_0} = \left[ {v\left( {{G_1}} \right),v\left( {{G_2}} \right)} \right]$ , 若 $M\left( G \right) \cap {E_0} =$ Ø，则

 $\begin{split} {\mu _s}\left( G \right) =& s\left( {M\left( G \right)} \right) = s\left( {M\left( G \right) \cap E\left( {{G_1}} \right)} \right) +\\& s\left( {M\left( G \right) \cap E\left( {{G_2}} \right)} \right)\leqslant {\mu _s}\left( {{G_1}} \right) + {\mu _s}\left( {{G_2}} \right) \end{split}$

$M\left( G \right) \cap {E_0} \ne$ Ø，由于 ${G_1}$ 有完美 ${K_{1,s}}$ −匹配，而 $M\left( G \right) \cap {E_0} \ne$ Ø，故 ${G_1}$ 中有点未被 $M\left( G \right) \cap E\left( {{G_1}} \right)$ 覆盖，所以， $M\left( G \right) \cap E\left( {{G_1}} \right)$ 不是 ${G_1}$ 的最大 ${K_{1,s}}$ −匹配，从而有 $s\left( {M\left( G \right) \cap E\left( {{G_1}} \right)} \right) < {\mu _s}\left( {{G_1}} \right)$ ，即 $s( M\left( G \right) \cap E\left( {{G_1}} \right) )$ ${\mu _s}\left( {{G_1}} \right) - 1$ ，故有

 $\begin{split} &{\mu _s}\left( G \right) = s\left( {M\left( G \right)} \right)\leqslant{\mu _s}\left( {{G_1}} \right) - 1 + 1 +\\ &\quad{\mu _s}\left( {{G_2}} \right) = {\mu _s}\left( {{G_1}} \right) + {\mu _s}\left( {{G_2}} \right) \end{split}$

 $\varepsilon \left( G \right)\geqslant{\mu _s}\left( G \right)\varepsilon \left( {{K_{1,s}}} \right) = 2{\mu _s}\left( G \right)\sqrt s$

$\varepsilon \left( G \right)$ $2\sqrt s {\mu _s}\left( G \right)$ 成立。

a. ${\mu _s}\left( G \right) = {\mu _s}\left( H \right) + {\mu _s}\left( K \right)$ , ${c_1}\left( G \right) = {c_1}\left( H \right) + {c_1}\left( K \right)$ , 且 $H$ $K$ 都满足能量 ${K_{1,s}}$ −匹配条件；

b. ${\mu _s}\left( G \right) \!=\! {\mu _s}\left( H \right)\! +\! {\mu _s}\left( K \right)$ ${c_1}\left( G \right) \!=\! {c_1}\left( H \right)\! +\! {c_1}\left( K \right)\! +\! 1$ K满足能量 ${K_{1,s}}$ −匹配条件，且

 $\varepsilon \left( H \right) \geqslant 2\sqrt s {\mu _s}\left( H \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( H \right) + \dfrac{{\sqrt 5 }}{5}$

 $\varepsilon \left( G \right)2\sqrt s {\mu _s}\left( G \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( G \right)$

 $\begin{array}{l} \varepsilon \left( H \right)\geqslant2\sqrt s {\mu _s}\left( H \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( H \right)\\ \varepsilon \left( K \right)\geqslant2\sqrt s {\mu _s}\left( K \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( K \right) \end{array}$

 $\varepsilon \left( G \right)\geqslant\varepsilon \left( {G - {E_0}} \right) = \varepsilon \left( H \right) + \varepsilon \left( K \right)$

 ${\mu _s}\left( G \right) = {\mu _s}\left( H \right) + {\mu _s}\left( K \right), \;{c_1}\left( G \right) = {c_1}\left( H \right) + {c_1}\left( K \right)$

$\varepsilon \left( G \right)$ $2\sqrt s {\mu _s}\left( G \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( G \right)$

b. 设 ${E_0} = \left[ {v\left( H \right),v\left( K \right)} \right]$ ，由于

 $\begin{array}{l} \varepsilon \left( G \right)\geqslant \varepsilon \left( {G - {E_{\rm{0}}}} \right) = \varepsilon \left( H \right) + \varepsilon \left( K \right)\\ \varepsilon \left( H \right)\geqslant 2\sqrt s {\mu _s}\left( H \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( H \right) + \dfrac{{\sqrt 5 }}{5}\\ \varepsilon \left( K \right)\geqslant2\sqrt s {\mu _s}\left( K \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( K \right) \end{array}$

 ${\mu _s}\left( G \right) = {\mu _s}\left( H \right) + {\mu _s}\left( K \right), \;{c_1}\left( G \right) = {c_1}\left( H \right) + {c_1}\left( K \right) + 1$

 $\begin{split} &\varepsilon \left( G \right)\geqslant 2\sqrt s \left( {{\mu _s}\left( H \right) + {\mu _s}\left( K \right)} \right) + \quad\quad\\ &\quad\dfrac{{\sqrt 5 }}{5}\left( {{c_1}\left( H \right) + {c_2}\left( K \right) + 1} \right)= 2\sqrt s {\mu _s}\left( G \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( G \right) \end{split}$

$\varepsilon \left( G \right)$ $2\sqrt s {\mu _s}\left( G \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( G \right)$

a. ${E_0} = \left[ {v\left( {{G_1}} \right),v\left( {{G_2}} \right)} \right]$ 是一个星图；

b. ${E_0}$ 中的边均是 $G$ 的割边；

c. ${G_1}$ 有完美 ${K_{1,s}}$ −匹配；

d. ${G_1}$ ${G_2}$ 满足能量 ${K_{1,s}}$ −匹配条件；

$\varepsilon \left( G \right)$ $2\sqrt s {\mu _s}\left( G \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( G \right)$

 ${\mu _{\rm{s}}}\left( G \right) = {\mu _s}\left( {{G_1}} \right) + {\mu _s}\left( {{G_2}} \right),\;\;\;\;\;\;{c_1}\left( G \right) = {c_1}\left( {{G_1}} \right) + {c_1}\left( {{G_2}} \right)$

 $\begin{array}{l} \varepsilon \left( {{G_{\rm{1}}}} \right)\geqslant 2\sqrt s {\mu _s}\left( {{G_1}} \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( {{G_1}} \right)\\ \varepsilon \left( {{G_{\rm{2}}}} \right)\geqslant 2\sqrt s {\mu _s}\left( {{G_2}} \right) + \dfrac{{\sqrt 5 }}{5}{c_1}\left( {{G_2}} \right) \end{array}$

 $\varepsilon \left( G \right)\geqslant\; \varepsilon \left( {G{\rm{ - }}{E_0}} \right) = \varepsilon \left( {{G_1}} \right) + \varepsilon \left( {{G_2}} \right)$

 $\varepsilon \left( G \right)\geqslant 2\sqrt s {\mu _s}\left( G \right) + \frac{{\sqrt 5 }}{5}{c_1}\left( G \right)$

 ${\varepsilon ^{\rm{2}}}\left( G \right)\geqslant \frac{{8{m^3}}}{{2\displaystyle\sum\limits_{i = 1}^n {{{{{d_i}} }^2}} - 2m + 8q}}$

 ${M_2}\left( G \right) = 2m$ (2)
 ${M_4}\left( G \right) = 2{\sum\limits_{i = 1}^n { {{d_i}} } ^2} - 2m + 8q$ (3)

$G$ 的度序列记为{ ${d_{\rm{1}}},{d_2},\cdots,{d_n}$ }，记最大度为 $\varDelta \left( G \right)$ ，则有

 ${d_1}^2 + {d_2}^2 + \cdots + d_n^2 \leqslant 2m\left( {\varDelta \left( G \right) + 1} \right) - n\varDelta \left( G \right)$

 ${\varepsilon ^{\rm{2}}}\left( G \right)\geqslant \frac{{{{\left( {{M_2}\left( G \right)} \right)}^3}}}{{{M_4}\left( G \right)}} = \frac{{8{m^3}}}{{2\displaystyle\sum\limits_{i = 1}^n { {{d_i}^2}} - 2m + 8q}}$ (4)

$G$ 是一棵最大度不超过3的树，可以得到这类图的关于星匹配数的能量下界。

 $\begin{split} {\varepsilon ^2}\left( T \right)\geqslant& \frac{{4{m^3}}}{{\displaystyle\sum\limits_{i = 1}^n {{{ {{d_i}} }^2}} - m}}\geqslant \frac{{4{{\left( {n - 1} \right)}^3}}}{{\left( {2d + 1} \right)\left( {n - 1} \right) - dn}} =\\& \frac{{4{{\left( {n - 1} \right)}^3}}}{{d\left( {n - 2} \right)+n - 1}} \geqslant \frac{{4{{\left( {n - 1} \right)}^3}}}{{\left( {d + 1} \right)\left( {n - 1} \right)}} = \\&\frac{{4{{\left( {n - 1} \right)}^2}}}{{d + 1}}\geqslant {\left( {n - 1} \right)^2} \end{split}$

$\varepsilon \left( T \right)$ $n - 1$

$T$ 有完美 ${K_{1,s}}$ −匹配时，则 ${\mu _s}\left( T \right) =m\left( T \right) =$ $\dfrac{n}{{s + 1}}$ （其中，树 $T$ 最大度为 $s$ ，即 $\varDelta \left( T \right) = s$ ）。若 $T$ 无完美 ${K_{1,s}}$ −匹配，则有 ${\mu _s}\left( T \right) < \dfrac{n}{{s + 1}}$ ，故对任意 $n$ 阶树 $T$ ，均有 ${\mu _s}\left( T \right)$ $\dfrac{n}{{s + 1}}$ ，即 $n$ $\left( {s + 1} \right){\mu _s}\left( T \right)$ ，从而 $\varepsilon \left( T \right)$ $n - 1$ ，故 $\varepsilon \left( T \right)$ $\left( {s + 1} \right){\mu _s}\left( T \right) - 1$

 [1] 何常香, 刘世琼. 星匹配数与(无符号)拉普拉斯特征值[J]. 高校应用数学学报, 2015, 30(3): 333-339. [2] WONG D, WANG X L, CHU R. Lower bounds of graph energy in terms of matching number[J]. Linear Algebra and its Applications, 2018, 549(2): 276-286. [3] CAPOROSSI G, CVETKOVIĆ D, GUTMAN I, et al. Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy[J]. Journal of Chemical Information and Modeling, 1999, 39(6): 984-996. [4] RADA J. Lower bounds for the energy of digraphs[J]. Linear Algebra and its Applications, 2010, 432(9): 2174-2180. DOI:10.1016/j.laa.2009.02.007 [5] RADA J, TINEO A. Upper and lower bounds for the energy of bipartite graphs[J]. Journal of Mathematical Analysis and Applications, 2004, 289(2): 446-455. DOI:10.1016/j.jmaa.2003.08.027 [6] ZHOU B. Lower bounds for the energy of qusdrangle-free graphs[J]. MATCH Commun Math Comput Chem, 2006, 55(1): 91-94. [7] ZHOU B, GUTMAN I, DE LA PEÑA J A, et al. On spectral moments and energy of graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2007, 57(1): 183-191. [8] DAY J, SO W. Graph energy change due to edge deletion[J]. Linear Algebra and its Applications, 2008, 428(8/9): 2070-2078.