The Laplacian spectral radii ordering of unbalanced signed bicyclic graphs
-
摘要: 研究了非平衡符号双圈图的第一到第六大的拉普拉斯特征值的分布规律,完善了现有结论中一些不准确的情况,推广了现有的结果,并给出了取得极值情况的图例。Abstract: In this paper, the distribution law of the Laplacian eigenvalues from the first to the sixth of the unbalanced signed bicyclic graphs is studied, some inaccuracies of the existing conclusions are corrected, the existing results are generalized, and the legend of the extreme value is given.
-
0. 引言
令$ G=\left(V\left(G\right), E\left(G\right)\right) $是一个简单图,$ \sigma :E\left(G\right)\to \left\{+1, -1\right\} $是边集$ E\left(G\right) $上的一个映射。称$ \varGamma =\left(G, \sigma \right) $是一个符号图,其中$ G $是符号图$ \varGamma $的基础图,$ \sigma $是符号图$ \varGamma $的符号函数。显然,$ G $和符号图$ \varGamma $有相同的顶点集,即$ V\left(G\right)=V\left(\varGamma \right) $;同时边数相等,即$ \left|V\right(G\left)\right|=\left|V\right(\varGamma \left)\right| $。对于任意的边$ e={v}_{i}{v}_{j}\in E\left(G\right) $,若$ \sigma \left(e\right)=+1 $(或$ \sigma \left(e\right)=-\mathrm{ }1) $,则称边$ e $是正的(或负的)。为了方便,用实边和虚边分别代表正边和负边。显然符号图$ \varGamma $是特殊的赋权图。
如果一个圈中包含偶数条负边,则称该圈为正圈;否则称为负圈。或者把符号图$ \varGamma $中圈$ C $的符号记为$ \sigma \left(C\right)=\prod \limits_{e\in C}\sigma \left(e\right) $,则有$ \sigma \left(C\right)=\left\{\begin{array}{l}+1\\ -1\end{array}\right. $,所以称符号为$ +\left(-\right) $的圈称为正(负)圈。如果一个符号图$ \varGamma $中所有的圈都为正圈,则称该符号图$ \varGamma $是平衡的;否则称为非平衡的。
令$ \varGamma =\left(G, \sigma \right) $是一个符号图,$ \varGamma $的顶点集$ V\left(\varGamma \right)=\left\{{v}_{1}, {v}_{2}, \dots , {v}_{n}\right\} $,则$ \varGamma $的拉普拉斯矩阵为$ \boldsymbol{L}\left(\varGamma \right)=\boldsymbol{D}\left(\varGamma \right)-\boldsymbol{A}\left(\varGamma \right) $,其中, $ \boldsymbol{D}\left(\varGamma \right)=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\left({d}_{{v}_{1}}, {d}_{{v}_{2}}, \dots , {d}_{{v}_{n}}\right) $表示度对角矩阵,这里的$ {d}_{{v}_{i}}={d}_{{v}_{i}}^{+}+{d}_{{v}_{i}}^{-} $,$ {d}_{{v}_{i}}^{+} $表示与$ \varGamma $的正边重合的顶点$ {v}_{i} $的度;$ {d}_{{v}_{i}}^{-} $表示与$ \varGamma $的负边重合的顶点$ {v}_{i} $的度,可参考文献[1]。$ \mathrm{其}\mathrm{中}\boldsymbol{A}\left(\varGamma \right)=\left({a}_{ij}^{\sigma }\right) $,这里的$ {a}_{ij}^{\sigma }=\sigma \left({v}_{i}{v}_{j}\right)\bullet {a}_{ij},{a}_{ij}=1 $当且仅当$ {v}_{i} $与$ {v}_{j} $邻接;否则$ {a}_{ij}=0 $。符号图$ \varGamma $的拉普拉斯矩阵是实对称的半正定矩阵,记符号图$ \varGamma $的拉普拉斯特征多项式为
$$ {\phi }_{L}\left(\varGamma , x\right)=\phi \left(\varGamma , x\right)=\mathrm{d}\mathrm{e}\mathrm{t}\left(x\boldsymbol{I}-\boldsymbol{L}\left(\varGamma \right)\right) 。 $$ 拉普拉斯特征值为
$$ 0\le {\lambda }_{1}\left(\varGamma \right)\le {\lambda }_{2}\left(\varGamma \right)\le \dots \le {\lambda }_{n-1}\left(\varGamma \right)\le {\lambda }_{n}\left(\varGamma \right) \text{,} $$ 其中把$ {\lambda }_{n}\left(\varGamma \right) $称为符号图$ \varGamma $的拉普拉斯谱半径。
1981年$ \mathrm{C}\mathrm{v}\mathrm{e}\mathrm{t}\mathrm{k}\mathrm{o}\mathrm{v}\mathrm{i}\mathrm{ć} $指出了图谱理论中研究的12个方向,其中之一就是依图的谱对图进行分类和排序,具体见文献[2-4]。而较多的就是对图的拉普拉斯谱进行研究:Yu等[5]按树的拉普拉斯谱半径对树进行排序;Belardo和Zhou[6]得到了给定阶数的非平衡符号单圈图中,最小拉普拉斯特征值最大和最小的图;Belardo等[7]得到了在$ n $阶($ n\ge 5 $)非平衡符号双圈图中,最小拉普拉斯特征值最小的图。关于符号图的一些结论可参考文献[8-10],关于符号图的拉普拉斯谱的结论可参考文献[1, 11]。
对于平衡的符号双圈图,Belardo和Zhou[6]给出了关于其最大拉普拉斯特征值前四大的图。关于符号图平衡性的相关结论可参考文献[12-15]。对于非平衡的符号双圈图,何常香等[16]给出了所有非平衡符号双圈图构成的集合中,最大拉普拉斯特征值前四大的图,并给出了这些最大拉普拉斯特征值所对应的极图。在上述文献中,作者首先从10个非平衡的符号双圈图中找出拉普拉斯特征值最大的一个作为第一大类极图,利用夺邻变换,得到第一大类极图的上一步图,共有5个,从中确定出最大的为$ {\varGamma }_{1}^{4} $,并与剩下的9个极图中最大的极图$ {\varGamma }_{2} $进行比较,得出拉普拉斯特征值较大的极图作为第二大类极图,以此类推。文章的方法是可行的,但在确定通过夺邻变换后得到的第一大类极图的上一步图中的最大极图时,由于计算错误,而应该最大的为$ {\varGamma }_{1}^{1} $,又由于图$ {\varGamma }_{1}^{1} $的最大拉普拉斯特征值大于图$ {\varGamma }_{2} $的最大拉普拉斯特征值,故第二大类极图将是$ {\varGamma }_{1}^{1} $。故在本文中,重新给出所有非平衡符号双圈图构成的集合中,最大拉普拉斯特征值前六大的图,并给出了这些最大拉普拉斯特征值所对应的极图。
1. 定义和引理
假设$ \theta :V\left(G\right)\to \left\{+1, -1\right\} $是作用在顶点集上的任意函数,现定义一个新的符号图$ {\varGamma }^{\theta }=\left(G, {\sigma }^{\theta }\right) $,其中$ G $是符号图$ {\varGamma }^{\theta } $的基础图,$ {\sigma }^{\theta } $是$ {\varGamma }^{\theta } $的符号函数,满足对于任意的边$ uv $,有$ {\sigma }^{\theta }\left(uv\right)=\theta \left(u\right)\sigma \left(uv\right)\theta \left(v\right) $。现在定义一个对角阵$ {\boldsymbol{D}}^{\theta }=\left({d}_{i}\right) $,满足对每个点$ v\in V\left(G\right) $,有$ {d}_{i}=\theta \left(v\right) $,则$ \boldsymbol{A}\left({\varGamma }^{\theta }\right)={\boldsymbol{D}}^{\theta }\boldsymbol{A}\left(\varGamma \right){\boldsymbol{D}}^{\theta } $成立。
由此对具有相同特征值和相同的拉普拉斯特征值的交换等价图进行定义。
定义1[16] 设$ {\varGamma }_{1} $是非平衡的符号图,若存在函数$ \theta $满足$ {\varGamma }_{2}={{\varGamma }_{1}}^{\theta } $或者满足$ \boldsymbol{A}\left({\varGamma }^{\theta }\right)={\boldsymbol{D}}^{\theta }\boldsymbol{A}\left(\varGamma \right){\boldsymbol{D}}^{\theta } $,则称$ {\varGamma }_{1} $与$ {\varGamma }_{2} $是交换等价的,记为$ {\varGamma }_{1} \sim {\varGamma }_{2} $。
由于$ \boldsymbol{D}\left({\varGamma }^{\theta }\right)={\boldsymbol{D}}^{\theta }\boldsymbol{D}\left(\varGamma \right){\boldsymbol{D}}^{\theta } $,$ \boldsymbol{A}\left({\varGamma }^{\theta }\right)={\boldsymbol{D}}^{\theta }\boldsymbol{A}\left(\varGamma \right){\boldsymbol{D}}^{\theta } $,等号两边分别相减,得$ \boldsymbol{D}\left({\varGamma }^{\theta }\right)-\boldsymbol{A}\left({\varGamma }^{\theta }\right)=\boldsymbol{L}\left({\varGamma }^{\theta }\right)={\boldsymbol{D}}^{\theta }\boldsymbol{D}\left(\varGamma \right){\boldsymbol{D}}^{\theta }-{\boldsymbol{D}}^{\theta }\boldsymbol{A}\left(\varGamma \right){\boldsymbol{D}}^{\theta }={\boldsymbol{D}}^{\theta }\left(\boldsymbol{D}\left(\varGamma \right)-\boldsymbol{A}\left(\varGamma \right)\right){\boldsymbol{D}}^{\theta }={\boldsymbol{D}}^{\theta }\boldsymbol{L}\left({\varGamma }^{\theta }\right){\boldsymbol{D}}^{\theta } $。因此定义1等价于:若存在函数$ \theta $满足$ {\varGamma }_{2}={{\varGamma }_{1}}^{\theta } $, 或者满足$ \boldsymbol{L}\left({\varGamma }^{\theta }\right)={\boldsymbol{D}}^{\theta }\boldsymbol{L}\left(\varGamma \right){\boldsymbol{D}}^{\theta } $,则称$ {\varGamma }_{1} $与$ {\varGamma }_{2} $是交换等价的,记为$ {\varGamma }_{1}~{\varGamma }_{2} $。
推论1 设$ \varGamma =\left(G, \theta \right) $为一个有$ n $个顶点的符号图,且$ H $为$ G $的子图(至少有2个顶点),$ H $与$ \varGamma -H $有唯一一个顶点$ v $相连,且$ N\left(v\right)=\left\{{v}_{1}, {v}_{2}, \mathrm{ }\dots , {v}_{k}\right\}\left(k\ge 1\right) $,其中$ v{v}_{1}, v{v}_{2}, \dots , v{v}_{k} $都是悬挂边。若$ \boldsymbol{L}\left({H}_{{\varGamma }^{\theta }}\right)={\boldsymbol{D}}^{\theta }\boldsymbol{L}\left({H}_{\varGamma }\right){\boldsymbol{D}}^{\theta } $或者$ {H}_{\varGamma }={H}_{{\varGamma }^{\theta }} $成立,则$ \varGamma \sim {\varGamma }^{\theta } $。
引理1[16] 令$ \varGamma =\left(G, \theta \right) $是一个有$ n $个顶点的符号图,包含子图$ H $(至少有2个顶点)和与顶点$ v $相连的$ n-\left|H\right| $条不同的悬挂边(不在$ H $中),其中$ v\in V\left(H\right) $,则
$$ \varPhi \left(\varGamma , x\right)={\left(x-1\right)}^{n-\left|H\right|}\varPhi \left(H, x\right)-\left(n-\left|H\right|\right)x{\left(x-1\right)}^{n-\left|H\right|-1}\varPhi \left({\boldsymbol{L}}_{v}\left(H\right), x\right), $$ 其中$ {\boldsymbol{L}}_{v}\left(H\right) $表示从$ \boldsymbol{L}\left(H\right) $删去顶点$ v $所在的行和列后所得的主子矩阵。
下面介绍一种更加简单的方法来计算图的拉普拉斯矩阵对应的特征多项式。
定义2[17] 把任意图中有相同邻集的点称为双胞胎点。
引理2[17] $ G $是一个有$ k $(度都为$ d $)个不相邻的双胞胎点,则$ d $是$ \boldsymbol{L}\left(G\right) $的特征值,且重数至少为$ k-1 $。
为了得到特征多项式,需要先将图进行等价划分[18],进而每个等价划分后的图都有等价划分矩阵$ \boldsymbol{Q} $,通过直接计算得到矩阵$ \boldsymbol{Q} $的特征多项式$ \varPhi \left(\boldsymbol{Q}, x\right) $,再根据引理2得到下面的结论。
引理3 图$ G $的拉普拉斯矩阵对应的特征多项式为$ \prod \limits_{i=1}^{t}{\left(x-{d}_{i}\right)}^{\sum ({k}_{i}-1)}\bullet \varPhi \left(\boldsymbol{Q}, x\right) $。其中$ {d}_{i} $表示有$ {k}_{i} $个不相邻的双胞胎点的度,$ \sum ({k}_{i}-1) $表示对特征值$ {d}_{i} $的重数$ {k}_{i}-1 $进行求和。
引理4[16] 令$ \varGamma =\left(G, \theta \right) $是一个有$ n $个顶点的符号图,$ \lambda \left(\varGamma \right) $是$ \varGamma $的最大拉普拉斯特征值,且$ \Delta $是$ \varGamma $的最大顶点度,则$ \lambda \left(\varGamma \right)\ge \Delta +1 $。
下面的引理称为夺邻变换,即被删去的边属于悬挂边时,最大拉普拉斯特征值的变化情况。
引理5[19] 令$ \varGamma =\left(G, \theta \right) $是一个有$ n $个顶点的符号图,$ u, v $是$ \varGamma $中的2个顶点,$ v{v}_{1}, v{v}_{2}, \dots , v{v}_{k}\left(k\ge 1\right) $是$ \varGamma $中的悬挂边,且$ x $是属于最大拉普拉斯特征值的特征向量,令
$$ {\varGamma }^{\text{'}}=\varGamma -v{v}_{1}-v{v}_{2}-\dots -v{v}_{k}+u{v}_{1}+u{v}_{2}+\dots +u{v}_{k} $$ 变换后的符号图中的边保持原来的符号。若$ {x}_{u}\ge {x}_{v}\ge 0 $或$ {x}_{u}\le {x}_{v}\le 0 $,有$ \lambda \left({\varGamma }^{\text{'}}\right)\ge \lambda \left(\varGamma \right) $;进一步若$ {x}_{u} > {x}_{v}\ge 0 $或$ {x}_{u} < {x}_{v}\le 0 $,有$ \lambda \left({\varGamma }^{\text{'}}\right) > \lambda \left(\varGamma \right) $。
下面引理考虑的情况是:如果被删去的边不属于悬挂边,即为非割边或非悬挂边时,最大拉普拉斯特征值的变化。
定义3[6] 令$ \varGamma =\left(G, \theta \right) $是一个有$ n $个顶点的符号图,$ uv $是$ \varGamma $中的一条非悬挂边,且$ uv $不在任何一个三角形中。令$ N\left(v\right)\backslash \left\{u\right\}=\left\{{v}_{1}, {v}_{2}, \dots , {v}_{d}\right\}\left(d\ge 1\right) $,符号图
$$ \begin{array}{l}{\varGamma }^{\text{'}}=\alpha \left(\varGamma , uv\right)=\varGamma -v{v}_{1}-v{v}_{2}-\dots -v{v}_{d}+u{v}_{1}+\\ u{v}_{2}+\dots +u{v}_{d}\end{array} $$ 称$ {\varGamma }^{\text{'}} $是$ \varGamma $在边$ uv $上的一个$ \alpha $-变换。
引理6[16] 令$ uv $是符号图$ \varGamma $中的一条边,$ {\varGamma }^{\text{'}}=\alpha \left(\varGamma , uv\right) $是由$ \varGamma $在边$ uv $上进行$ \alpha $-变换得到的符号图。令$ x $是属于最大拉普拉斯特征值的特征向量。若$ {x}_{u}{x}_{v}\ge 0 $,则有$ \lambda \left({\varGamma }^{\text{'}}\right)\ge \lambda \left(\varGamma \right) $;进一步有若$ {x}_{u}{x}_{v} > 0 $,则有$ \lambda \left({\varGamma }^{\text{'}}\right) > \lambda \left(\varGamma \right) $。
引理7[16] 令$ \varGamma $是非平衡的$ \infty $-图,且$ \varGamma \notin {B}_{n}\left(\mathrm{3, 3}\right) $,则存在非平衡的$ \infty $-图$ {\varGamma }^{\text{'}} $,满足$ \left|V\left(\widehat{{\varGamma }^{\text{'}}}\right)\right| < \left|V\left(\widehat{\varGamma }\right)\right| $且$ \lambda \left({\varGamma }^{\text{'}}\right) > \lambda \left(\varGamma \right) $。
引理8[16] 令$ \varGamma $是非平衡的$ \theta $-图,且$ \varGamma \notin {B}_{n}\left({P}_{1}, {P}_{2}, {P}_{2}\right) $,则存在非平衡的$ \theta $-图$ {\varGamma }^{\text{'}} $,满足$ \left|V\left(\widehat{{\varGamma }^{\text{'}}}\right)\right| < \left|V\left(\widehat{\varGamma }\right)\right| $且$ \lambda \left({\varGamma }^{\text{'}}\right) > \lambda \left(\varGamma \right) $。
引理9 若$ \varGamma $是一个非平衡的哑铃图,且$ \varGamma \notin $ $ {B}_{n}\left(\mathrm{3, 1}, 3\right), \mathrm{则}\mathrm{存}\mathrm{在}\mathrm{非}\mathrm{平}\mathrm{衡}\mathrm{的}\mathrm{哑}\mathrm{铃}\mathrm{图} $ $ {\varGamma }^{\text{'}}\in {B}_{n}\left(p, l, q\right), $$ \mathrm{满}\mathrm{足} $ $ \left|V\left(\widehat{{\varGamma }^{\text{'}}}\right)\right| < \left|V\left(\widehat{\varGamma }\right)\right| $,则$ \lambda \left({\varGamma }^{\text{'}}\right) > \lambda \left(\varGamma \right) $成立。
证明 证明与文献[16]中的引理9方法类似。
推论2 若$ \varGamma \in {B}_{n}\left(p, l, q\right) $是一个非平衡的哑铃图,且$ \varGamma \notin {B}_{n}\left(\mathrm{3, 1}, 3\right) $,则当$ {\varGamma }^{\text{'}}\in {B}_{n}\left(\mathrm{3, 1}, 3\right) $时,有$ \lambda \left({\varGamma }^{\text{'}}\right) > \lambda \left(\varGamma \right) $成立。
引理10[20] 设$ G $是一个不同构于$ {P}_{\mathrm{1, 1}, n-2}^{1, n-4} $的简单连通图,$ {G}_{uv} $是由$ G $剖分边$ uv $后所得到的图,若$ uv $在$ G $的一条内部路上,则$ \lambda \left(G\right) > \lambda \left({G}_{uv}\right) $。其中$ {P}_{\mathrm{1, 1}, n-2}^{1, n-4} $是一个通过如下方式得到的$ 1+1+n-2 $阶树:对于每个$ i=\mathrm{1, 2} $,在$ {P}_{n-2} $的点$ {v}_{1}、{v}_{n-4} $处各粘合一个一阶悬挂路。
2. 非平衡符号双圈图的分类
称顶点数为$ n $,且边数为$ n+1 $的连通图$ G $称为双圈图。把基础图为双圈图的符号图称为符号双圈图。设$ G $是双圈图,$ G $的极小双圈子图称为$ G $的基,记为$ \widehat{G} $。若$ \varGamma =\left(G, \sigma \right) $,则称$ \widehat{\varGamma }=\left(\widehat{G}, \sigma \right) $为符号双圈图$ \varGamma $的极小双圈子图。显然可以知道$ G $可以看作由$ \widehat{G} $加上一些与$ \widehat{G} $恰有一个公共点的树而构成的图。
将$ \widehat{G} $进行分类:
第1类:$ B\left(p, q\right)\left(p\ge q\ge 3\right) $由具有唯一公共点(设为$ {v}_{1} $)的2个圈$ {C}_{p}, {C}_{q} $组成,称这类图为$ \mathrm{\infty } $-图(图 1)。
第2类:$ B\left(p, l, q\right)\left(p\ge q\ge 3\right) $由无公共顶点的圈$ {C}_{p}, {C}_{q} $通过一条长$ l\left(l\ge 1\right) $的路连接而成。称这类图为哑铃图;如果$ p=q=3 $,即$ {C}_{p}, {C}_{q} $为3圈,则称这类图为沙漏图(图 2)。
第3类:$ B\left({P}_{k}, {P}_{l}, {P}_{m}\right)\left(1\le m\le \mathrm{m}\mathrm{i}\mathrm{n}\left\{k, l\right\}\right) $,由连接点$ x $和$ y $的3条内部不相交的路连接而成。这3条路分别是长度为$ k $的路$ x{v}_{1}{v}_{2}\dots {v}_{k-1}y $,长度为$ l $的路$ x{u}_{1}{u}_{2}\dots {u}_{l-1}y $,长度为$ m $的路$ x{w}_{1}{w}_{2}\dots {w}_{m-1}y $,称这类图为$ \theta $-图(图 3)。
用$ {B}_{n} $来表示所有的非平衡符号双圈图的集合,根据$ \widehat{G} $的分类,下面对$ n $阶非平衡符号双圈图进行分类(图 4)。
$$ {B}_{n}\left(p, q\right)=\left\{\begin{array}{l}\varGamma =\left.\left(G, \sigma \right)\right|\widehat{G}=B\left(p, q\right), \\ p\ge q\ge 3\end{array}\right\} \text{,} $$ $$ {B}_{n}\left(p, l, q\right)=\left\{\begin{array}{l}\varGamma =\left.\left(G, \sigma \right)\right|\widehat{G}=B\left(p, l, q\right), \\ p\ge q\ge 3, l\ge 1\end{array}\right\} \text{,} $$ $$ {B}_{n}\left({P}_{k}, {P}_{l}, {P}_{m}\right)=\left\{\begin{array}{l}\varGamma =\left.\left(G, \sigma \right)\right|\widehat{G}=B\left({P}_{k}, {P}_{l}, {P}_{m}\right), \\ 1\le m\le \mathrm{m}\mathrm{i}\mathrm{n}\left\{k, l\right\}\end{array}\right\} 。 $$ 显然可以知道:$ {B}_{n}={B}_{n}\left(p, q\right)\bigcup {B}_{n}\left(p, l, q\right)\bigcup $ $ {B}_{n}\left({P}_{k}, {P}_{l}, {P}_{m}\right) $。
3. 结论及其证明
引理11 令$ {\varGamma }_{i}^{\mathrm{*}}\in {B}_{n}\left(i=\mathrm{1, 2}, \mathrm{3, 4}, \mathrm{5, 6}\right) $是如图 4中所示的非平衡符号双圈图,则$ \lambda \left({\varGamma }_{i}^{\mathrm{*}}\right) $是方程$ {f}_{i}\left(x\right)=0 $的最大根,其中
$$ {f}_{1}\left(x\right)={x}^{3}+\left(-n-4\right){x}^{2}+4nx-8 \text{,} $$ $$ {f}_{2}\left(x\right)={x}^{3}+\left(-n-5\right){x}^{2}+\left(4n+6\right)x-14 \text{,} $$ $$ {f}_{3}\left(x\right)=\left(x-3\right)\left[{x}^{3}+\left(-n-3\right){x}^{2}+3nx-8\right] \text{,} $$ $$ {f}_{4}\left(x\right)=\left[{x}^{4}+\left(-n-6\right){x}^{3}+\left(6n+8\right){x}^{2}+\left(-8n-4\right)x+12\right] \text{,} $$ $$ {f}_{5}\left(x\right)=\left(x-3\right)\left[{x}^{3}-8{x}^{2}+15x-4-\left(n-5\right)x\left(x-3\right)\right] \text{,} $$ $$ {f}_{6}\left(x\right)=\left(x-2\right)\left[{x}^{5}+\left(-n-6\right){x}^{4}+\left(7n+4\right){x}^{3}+\\ \left(-11n-2\right){x}^{2}+\left(4n+16\right)x-8\right] 。 $$ 进一步地,当$ n\ge 9 $时,$ \lambda \left({\varGamma }_{1}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{2}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{3}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{4}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{5}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。
证明 由引理1知$ {\varGamma }_{1}^{\mathrm{*}}、{\varGamma }_{2}^{\mathrm{*}} $、$ {\varGamma }_{3}^{\mathrm{*}} $、$ {\varGamma }_{4}^{\mathrm{*}} $、$ {\varGamma }_{5}^{\mathrm{*}} $和$ {\varGamma }_{6}^{\mathrm{*}} $的拉普拉斯特征多项式分别为
$$ \varPhi \left({\varGamma }_{1}^{\mathrm{*}}, x\right)=\\ {\left(x-1\right)}^{n-4}\left(x-2\right)\left[{x}^{3}+\left(-n-4\right){x}^{2}+4nx-8\right] \text{,} $$ $$ \varPhi \left({\varGamma }_{2}^{\mathrm{*}}, x\right)=\\ {\left(x-1\right)}^{n-4}\left(x-2\right)\left[{x}^{3}+\left(-n-5\right){x}^{2}+\left(4n+6\right)x-14\right] \text{,} $$ $$ \varPhi \left({\varGamma }_{3}^{\mathrm{*}}, x\right)={\left(x-1\right)}^{n-4}\left(x-3\right)\left[{x}^{3}+\left(-n-3\right){x}^{2}+3nx-8\right] \text{,} $$ $$ \varPhi \left({\varGamma }_{4}^{\mathrm{*}}, x\right)=\\ {\left(x-1\right)}^{n-4}\left[{x}^{4}+\left(-n-6\right){x}^{3}+\left(6n+8\right){x}^{2}+\left(-8n-4\right)x+12\right] \text{,} $$ $$ \varPhi \left({\varGamma }_{5}^{\mathrm{*}}, x\right)=\\ {\left(x-1\right)}^{n-4}\left(x-3\right)\left[{x}^{3}-8{x}^{2}+15x-4-\left(n-5\right)x\left(x-3\right)\right] \text{,} $$ $$ \varPhi \left({\varGamma }_{6}^{\mathrm{*}}, x\right)= {\left(x-1\right)}^{n-6}\left(x-2\right)\left[{x}^{5}+\left(-n-6\right){x}^{4}+\\ \left(7n+4\right){x}^{3}+\left(-11n-2\right){x}^{2}+\left(4n+16\right)x-8\right] 。 $$ (1) 比较$ \lambda \left({\varGamma }_{1}^{\mathrm{*}}\right) $与$ \lambda \left({\varGamma }_{2}^{\mathrm{*}}\right) $的大小。由于$ {\varGamma }_{2}^{\mathrm{*}} $是$ {\varGamma }_{1}^{\mathrm{*}} $的上一步图,即通过夺邻变换知$ \lambda \left({\varGamma }_{1}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{2}^{\mathrm{*}}\right) $。
(2) 比较$ \lambda \left({\varGamma }_{2}^{\mathrm{*}}\right) $与$ \lambda \left({\varGamma }_{3}^{\mathrm{*}}\right) $的大小。对$ \varPhi \left({\varGamma }_{2}^{\mathrm{*}}, x\right) $和$ \varPhi \left({\varGamma }_{3}^{\mathrm{*}}, x\right) $作差计算,得
$$ \varPhi \left({\varGamma }_{2}^{\mathrm{*}}, x\right)-\varPhi \left({\varGamma }_{3}^{\mathrm{*}}, x\right)={\left(x-1\right)}^{n-4}g\left(x\right) \text{,} $$ 其中$ g\left(x\right)=-{x}^{3}+7{x}^{2}+\left(n-18\right)x+4 $,由引理4知$ \lambda \left({\varGamma }_{3}^{\mathrm{*}}\right)\ge \Delta +1=n $。易得当$ x > \lambda \left({\varGamma }_{3}^{\mathrm{*}}\right) $时,有$ g\left(x\right) < 0 $,即$ \varPhi \left({\varGamma }_{2}^{\mathrm{*}}, x\right) < \varPhi \left({\varGamma }_{3}^{\mathrm{*}}, x\right) $。因此$ \lambda \left({\varGamma }_{2}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{3}^{\mathrm{*}}\right) $。
(3) 比较$ \lambda \left({\varGamma }_{3}^{\mathrm{*}}\right) $与$ \lambda \left({\varGamma }_{4}^{\mathrm{*}}\right) $的大小。对$ \varPhi \left({\varGamma }_{3}^{\mathrm{*}}, x\right) $和$ \varPhi \left({\varGamma }_{4}^{\mathrm{*}}, x\right) $作差计算,得
$$ \varPhi \left({\varGamma }_{3}^{\mathrm{*}}, x\right)-\varPhi \left({\varGamma }_{4}^{\mathrm{*}}, x\right)={\left(x-1\right)}^{n-4}g\left(x\right) \text{,} $$ 其中$ g\left(x\right)={x}^{2}+\left(-n-4\right)x+12 $,由引理4知$ \lambda \left({\varGamma }_{4}^{\mathrm{*}}\right)\ge \Delta +1=n $。易得当$ x > \lambda \left({\varGamma }_{4}^{\mathrm{*}}\right) $时,有$ g\left(x\right) < 0 $,即$ \varPhi \left({\varGamma }_{3}^{\mathrm{*}}, x\right) < \varPhi \left({\varGamma }_{4}^{\mathrm{*}}, x\right) $。因此$ \lambda \left({\varGamma }_{3}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{4}^{\mathrm{*}}\right) $。
(4) 比较$ \lambda \left({\varGamma }_{4}^{\mathrm{*}}\right) $与$ \lambda \left({\varGamma }_{5}^{\mathrm{*}}\right) $的大小。对$ \varPhi \left({\varGamma }_{4}^{\mathrm{*}}, x\right) $和$ \varPhi \left({\varGamma }_{5}^{\mathrm{*}}, x\right) $作差计算,得
$$ \varPhi \left({\varGamma }_{4}^{\mathrm{*}}, x\right)-\varPhi \left({\varGamma }_{5}^{\mathrm{*}}, x\right)={\left(x-1\right)}^{n-4}g\left(x\right) \text{,} $$ 其中$ g\left(x\right)=-{x}^{2}+nx=-x\left(x-n\right) $。显然当$ x > \lambda \left({\varGamma }_{5}^{\mathrm{*}}\right)\ge \Delta +1=n $时,$ -x\left(x-n\right) < 0 $成立,进而$ \varPhi \left({\varGamma }_{4}^{*}, x\right) < \varPhi \left({\varGamma }_{5}^{\mathrm{*}}, x\right) $,因此$ \lambda \left({\varGamma }_{4}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{5}^{\mathrm{*}}\right) $。
(5) 比较$ \lambda \left({\varGamma }_{5}^{\mathrm{*}}\right) $与$ \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $的大小。对$ \varPhi \left({\varGamma }_{5}^{\mathrm{*}}, x\right) $和$ \varPhi \left({\varGamma }_{6}^{\mathrm{*}}, x\right) $作差计算,得
$$ \varPhi \left({\varGamma }_{5}^{\mathrm{*}}, x\right)-\varPhi \left({\varGamma }_{6}^{\mathrm{*}}, x\right)={\left(x-1\right)}^{n-6}g\left(x\right) , $$ 其中$ g\left(x\right)=\left(6-n\right){x}^{4}+\left(3n-18\right){x}^{3}+\left(9-2n\right){x}^{2}+\left(12-n\right)x-4 $,当$ x > \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right)\ge \Delta +1=n-1 $时,$ g\left(x\right) < 0 $。进而$ \varPhi \left({\varGamma }_{5}^{\mathrm{*}}, x\right) < \varPhi \left({\varGamma }_{6}^{\mathrm{*}}, x\right) $,因此$ \lambda \left({\varGamma }_{5}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。
结论得证。
引理12 若$ \varGamma \in {B}_{n}\backslash \left\{\varGamma |\varGamma ~{\varGamma }_{3}^{\mathrm{*}}, \varGamma ~{\varGamma }_{5}^{\mathrm{*}}\right\} $是一个$ \mathrm{\infty } $-图,则$ \lambda \left(\varGamma \right) < \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。
证明 由引理4、6~7不难看出只需证明:若$ \varGamma \in \left\{{\varGamma }_{5}, {\varGamma }_{6}, {\varGamma }_{7}, {\varGamma }_{2}^{i}, {\varGamma }_{4}^{j}\right\}, \mathrm{ }1\le i\le 4,1\le j\le 6 $(可参考文献[16]),则有$ \lambda \left(\varGamma \right) < \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。
直接计算可知
$$ \begin{array}{l}\lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{7}\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\lambda \left({\varGamma }_{5}\right), \lambda \left({\varGamma }_{6}\right), \lambda \left({\varGamma }_{7}\right)\right\},\\ \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{2}^{1}\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\lambda \left({\varGamma }_{2}^{i}\right), 1\le i\le 4\right\}, \\ \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{4}^{1}\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\lambda \left({\varGamma }_{4}^{j}\right), 1\le j\le 6\right\}。\end{array} $$ 结论得证。
引理13 若$ \varGamma \in {B}_{n}\backslash \left\{\varGamma |\varGamma ~{\varGamma }_{1}^{\mathrm{*}}, \varGamma ~{\varGamma }_{2}^{\mathrm{*}}, \varGamma ~{\varGamma }_{4}^{\mathrm{*}}, \varGamma ~{\varGamma }_{6}^{\mathrm{*}}\right\} $是一个$ \theta $-图,则$ \lambda \left(\varGamma \right) < \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。
证明 只需考虑$ \varGamma \in \left\{{\varGamma }_{8}, {\varGamma }_{9}, {\varGamma }_{10}, {\varGamma }_{1}^{i}, {\varGamma }_{3}^{j}\right\}, i=\mathrm{2, 3}, 5\mathrm{ }; $ $ j=\mathrm{1, 2}, \dots , 7 $(可参考文献[16]),则有$ \lambda \left(\varGamma \right) < \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。通过计算可知
$$ \begin{array}{l}\lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{8}\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\lambda \left({\varGamma }_{8}\right), \lambda \left({\varGamma }_{9}\right), \lambda \left({\varGamma }_{10}\right)\right\}, \\ \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{1}^{2}\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\lambda \left({\varGamma }_{1}^{i}\right), i=\mathrm{2, 3}, 5\right\}, \\ \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{3}^{6}\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\lambda \left({\varGamma }_{3}^{j}\right), 1\le j\le 7\right\}。\end{array} $$ 引理14 若$ \varGamma \in {B}_{n} $是非平衡的哑铃图,则$ \lambda \left(\varGamma \right) < \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。
证明 由引理4、6、8~10知,只需要考虑$ \varGamma \in \left\{{\varGamma }_{2}^{5}, {\varGamma }_{4}^{7}, {\varGamma }_{4}^{8}\right\} $(可参考文献[16]),有$ \lambda \left(\varGamma \right) < \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。通过计算可知
$$ \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{2}^{5}\right) \text{,} \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{4}^{7}\right) \text{,} \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{4}^{8}\right) 。 $$ 结论得证。
定理1 令$ {\varGamma }_{i}^{\mathrm{*}}\in {B}_{n}\left(i=\mathrm{1, 2}, \mathrm{3, 4}, \mathrm{5, 6}\right) $是如图 4中所示的非平衡符号双圈图,则
(1) $ \lambda \left({\varGamma }_{i}^{\mathrm{*}}\right) $是方程$ {f}_{i}\left(x\right)=0 $的最大根,其中$ {f}_{i}\left(x\right)(i=1, \dots , 6) $与引理11相同。
(2) 当$ n\ge 9 $时,$ \lambda \left({\varGamma }_{1}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{2}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{3}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{4}^{\mathrm{*}}\right) > $ $ \lambda \left({\varGamma }_{5}^{\mathrm{*}}\right) > \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。
(3) 若$ \varGamma \in {B}_{n}\backslash \left\{\varGamma \right|\varGamma ~{\varGamma }_{1}^{\mathrm{*}}, \varGamma ~{\varGamma }_{2}^{\mathrm{*}}, \varGamma ~{\varGamma }_{3}^{\mathrm{*}}, \varGamma ~{\varGamma }_{4}^{\mathrm{*}}, \varGamma ~ $ $ {\varGamma }_{5}^{\mathrm{*}}, \varGamma ~{\varGamma }_{6}^{\mathrm{*}}\} $,则$ \lambda \left(\varGamma \right) < \lambda \left({\varGamma }_{6}^{\mathrm{*}}\right) $。
4. 结束语
本文给出了所有非平衡的符号双圈图构成的集合中最大拉普拉斯特征值前六大的图,并给出了相应的极图。本文的研究方法可能对于研究符号3圈图、符号多圈图及符号混合双圈图的拉普拉斯谱半径排序问题提供思路和方法
-
[1] HOU Y P, LI J S, PAN Y L. On the Laplacian eigenvalues of signed graphs[J]. Linear and Multilinear Algebra, 2003, 51(1): 21-30. doi: 10.1080/0308108031000053611 [2] 郭曙光. 谱半径前六位的n阶单圈图[J]. 高校应用数学学报(A辑), 2003, 18(4): 480-486. https://www.cnki.com.cn/Article/CJFDTOTAL-GXYZ200304015.htm [3] 亓静. 双圈图的邻接谱半径[D]. 上海: 同济大学, 2006. [4] 王兴科, 谭尚旺. 双圈图按谱半径的排序[J]. 数学学报, 2010, 53(3): 469-476. https://www.cnki.com.cn/Article/CJFDTOTAL-SXXB201003006.htm [5] YU A M, LU M, TIAN F. Ordering trees by their Laplacian spectral radii[J]. Linear Algebra and Its Applications, 2005, 405: 45-59. doi: 10.1016/j.laa.2005.02.043 [6] BELARDO F, ZHOU Y. Signed graphs with extremal least Laplacian eigenvalue[J]. Linear Algebra and Its Applications, 2016, 497: 167-180. doi: 10.1016/j.laa.2016.02.028 [7] BELARDO F, BRUNETTI M, CIAMPELLA A. Signed bicyclic graphs minimizing the least Laplacian eigenvalue[J]. Linear Algebra and Its Applications, 2018, 557: 201-233. doi: 10.1016/j.laa.2018.07.026 [8] ZASLAVSKY T. Signed graphs[J]. Discrete Applied Mathematics, 1982, 4(1): 47-74. doi: 10.1016/0166-218X(82)90033-6 [9] ZASLAVSKY T. Matrices in the theory of signed simple graphs[J]. Mathematics, 2013: 207-229. [10] FAN Y Z, WANG Y, WANG Y. A note on the nullity of unicyclic signed graphs[J]. Linear Algebra and Its Applications, 2013, 438(3): 1193-1200. doi: 10.1016/j.laa.2012.08.027 [11] BELARDO F, SIMIĆ S K. On the Laplacian coefficients of signed graphs[J]. Linear Algebra and Its Applications, 2015, 475: 94-113. doi: 10.1016/j.laa.2015.02.007 [12] HARARY F. On the notion of balance of a signed graph[J]. The Michigan Mathematical Journal, 1953, 2(2): 143-146. [13] BELARDO F. Balancedness and the least eigenvalue of Laplacian of signed graphs[J]. Linear Algebra and Its Applications, 2014, 446: 133-147. doi: 10.1016/j.laa.2014.01.001 [14] ROBERTS F S. On balanced signed graphs and consistent marked graphs[J]. Electronic Notes in Discrete Mathematics, 1999, 2: 94-105. doi: 10.1016/S1571-0653(04)00017-4 [15] AKIYAMA J, AVIS D, CHVÁTAL V, et al. Balancing signed graphs[J]. Discrete Applied Mathematics, 1981, 3(4): 227-233. doi: 10.1016/0166-218X(81)90001-9 [16] 何常香, 李玉莹, 王文燕. 非平衡符号双圈图的最大拉普拉斯特征值[EB/OL]. [2023-04-18]. http://kns.cnki.net/kcms/detail/31.1732.O1.20220509. 1103.012.html. [17] BARRETT W, EVANS E, HALL H T, et al. New conjectures on algebraic connectivity and the Laplacian spread of graphs[J]. Linear Algebra and Its Applications, 2022, 648: 104-132. doi: 10.1016/j.laa.2022.04.021 [18] GODSIL C, ROYLE G F. Algebraic graph theory[M]. New York: Springer-Verlag, 2001. [19] HE C X, SHAO J Y, HE J L. On the Laplacian spectral radii of bicyclic graphs[J]. Discrete Mathematics, 2008, 308(24): 5981-5995. doi: 10.1016/j.disc.2007.11.016 [20] 袁西英, 邵嘉裕. 图的特征值[M]. 上海: 同济大学出版社, 2018.
下载: