双圈图的补图的无符号拉普拉斯谱半径

The Signless Laplacian Spectral Radius of the Complement of Bicyclic Graphs

摘要: 设D(G)和A(G)分别是图G的度矩阵和邻接矩阵，则Q(G)=D(G)+A(G)就是G的无符号拉普拉斯矩阵。让U_n³是把n−3条悬挂边粘到3圈C₃上的一点后得到的单圈图，θ_n^∗是把n−4条悬挂边粘到θ (2,1,2)的一个三度点得到的双圈图。在这篇文章里我们证明了，取得最大无符号拉普拉斯谱半径的单圈图和双圈图分别是U_n³和θ_n^∗。

Abstract: Let D(G) and A(G) be degree matrix and adjacency matrix of graph G, respectively. Then the signless Laplacian matrix is defined as Q(G)=D(G)+A(G). Let U_n³ be the unicyclic graph ob-tained by attaching n−3 pendent edges to a vertex on C₃, and θ_n^∗ be the bicyclic graph ob-tained by attaching n−4 pendent edges to a vertex of degree 3 on θ (2,1,2). In this paper we show that the maximum signless Laplacian spectral radii are achieved uniquely by U_n³ and θ_n^∗ among all complements of unicyclic graphs and bicyclic graphs of order n, respectively.

1. 引言

设图 $G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个n个点的简单连通图，其边集为 $E\left(G\right)$ ，点集 $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ 。若两条边存在一个公共端点，则称这两条边是相邻的。图G中与点 $v_i$ 相关联的边的数目称为点 $v_i$ 的度，记作 $d\left(v_i\right)$ 。 $A\left(G\right)=\left(a_{ij}\right)$ 表示图G的邻接矩阵，它是一个n阶的 $\left(0,1\right)$ 方阵，其中点 $v_i$ 和点 $v_j$ 相邻接时， $a_{ij}=1$ ，否则 $a_{ij}=0$ 。 $D\left(G\right)=diag\left(d\left(v_1\right),d\left(v_2\right),\cdots ,d\left(v_n\right)\right)$ 为图G的度对角矩阵， $Q\left(G\right)=D\left(G\right)+A\left(G\right)$ 称为图G的无符号拉普拉斯矩阵。因为 $D\left(G\right)+A\left(G\right)$ 为非负的实对称矩阵，所以它的特征值为实数。不失一般性，按照它们从大到小的顺序进行排序为：

$q_1\left(G\right)\ge q_2\left(G\right)\ge \cdots \ge q_n(\; G\; )$

其中最大的特征值 $q_1\left(G\right)$ 为图G的无符号拉普拉斯谱半径，简记作 $q\left(G\right)$ 。

近年来，由于发现图的无符号拉普拉斯谱与图的某些不变量之间有着密切的联系，越来越多的学者对此进行了研究，当图是二部图时，拉普拉斯矩阵和无符号拉普拉斯矩阵有相同的谱，从而无符号拉普拉斯谱半径的研究是非常有价值的。T. Chang和B. Tam [1] 刻画了具有最大无符号拉普拉斯谱半径的极图。Y. Huang等 [2] 确定了带有给定度序列的双圈图在取得最大无符号拉普拉斯谱半径的极图。关于这个问题有专门的研究报告 [3] 。一些学者认为，与拉普拉斯谱和邻接谱相比，无符号拉普拉斯谱在研究图性质方面更方便 [4] 。

边数等于点数的连通图是单圈图，边数等于点数加一的连通图是双圈图。令 $C_n$ 和 $p_n$ 分别表示n个点的圈和路，我们定义图 $b\left(p,l,q\right)$ 是由两个点不交的圈 $C_p$ ， $C_q$ 和一条路 $P_l$ 组成的图形，其中 $P_l$ 的两个端点分别和 $C_p$ ， $C_q$ 有一个公共点，而当 $C_p$ 和 $C_q$ 有唯一的公共点时，我们记这个图形为 $b\left(p,0,q\right)$ 。图 $b\left(p,l,q\right)$ 和 $b\left(p,0,q\right)$ 统称为b图。定义图 $\theta \left(p,l,q\right)$ (也简称 $\theta$ 图)为给定两个点中间连接有三条路 $P_{p+1}$ ， $P_{l+1}$ 和 $P_{q+1}$ ，其中这三条路两两之间除了两个给定的点外没有公共点。我们把 $b\left(p,l,q\right)$ 和 $b\left(p,0,q\right)$ 粘上一些树构成的图形记作 $B_n$ ，把 $\theta \left(p,l,q\right)$ 粘上一些树构成的图形记作 $\Theta \left(p,l,q\right)$ 。显然，所有n个点的双圈图由 $B_n$ 和 ${\Theta }_n$ 组成。

设 $U_n^3$ 是将 $n-3$ 悬挂边粘到三长圈 $C_3$ 的一个点上得到的，设 ${\theta }_n^{\ast }$ 是将 $n-4$ 条悬挂边粘到 $\theta \left(2,1,2\right)$ 的一个三度点得到的双圈图。本文我们证明了，n个点的单圈图的补图的最大无符号拉普拉斯谱半径只在 $\overline{U_n^3}$ 取到，n个点的双圈图的补图的最大无符号拉普拉斯谱谱半径只在 $\overline{{\theta }_n^{\ast }}$ 取到。

2. 主要结果

下面的定理在矩阵的研究中起到了非常重要的作用。

非负矩阵的Perron-Frobenius定理 [5] ：如果M是一个 $n\times n$ 阶的非负不可约矩阵，那么有以下结论成立：

1) 若 $\rho \left(M\right)$ 是矩阵A的最大特征值，则 $\rho \left(M\right)\ge 0$ ；

2) $\rho \left(M\right)$ 是矩阵A的单重根；

3) M有对应于特征值 $\rho \left(M\right)$ 的一个正的特征向量，使得 $Mx=\rho \left(M\right)x$ 。

众所周知图G是连通图的充分必要条件是图G对应的邻接矩阵是不可约的。

假设M是一个n阶的实对称矩阵， $\rho \left(M\right)$ 是它的最大特征值，x是一个n维的正单位向量。如果 $\rho \left(M\right)=x^{\text{T}}Mx$ 成立，则有 $Mx=\rho \left(M\right)x$ 。

设图G与其补图 $\bar{G}$ 都是连通的，接下来我们将 $Q\left(\bar{G}\right)$ 的对应于 $\mu \left(\bar{G}\right)$ 的特征向量用 $\bar{x}\left(G\right)={\left\{{\bar{x}}_v\left(G\right)|v\in V\left(G\right)\right\}}^{\text{T}}$ 表示，其中 ${\bar{x}}_v\left(G\right)$ 对应点v。

引理2.1假设u和v是图G的两个不同的点， $\left\{v_i|i=1,2,\cdots ,s\right\}\subseteq N_G\left(v\right)\backslash N_G\left(u\right)$ ，其中 $N_G\left(v\right)$ 表示点v的邻点集，令 $G^{\ast }=G-{\displaystyle {\sum }_{1\le i\le s}{v}_{i}v}+{\displaystyle {\sum }_{1\le i\le s}{v}_{i}u}$ 。如果 $x_u\left(\bar{G}\right)\le x_v\left(\bar{G}\right)$ 成立，那么 $q\left(\bar{G}\right)<q\left(\overline{G^{\ast }}\right)$ 。

证明：由定义显然有

$Q\left(\bar{G}\right)=\left(n-1\right)I-D\left(G\right)+J-I-A(\; G\; )$

和

$Q\left(\overline{G^{\ast }}\right)=\left(n-1\right)I-D\left(G^{\ast }\right)+J-I-A(\; G\; \ast \; )$

成立，其中I和J分别是单位矩阵和全一矩阵。为方便起见我们令 $\bar{x}=x\left(\bar{G}\right)$ ， ${\bar{x}}_v=x_v\left(\bar{G}\right)$ 。

则有

$\begin{array}{c}{\bar{x}}^{\text{T}}\left(Q\left(\bar{G}\right)-Q\left(\overline{G^{\ast }}\right)\right)\bar{x}={\bar{x}}^{\text{T}}\left(D\left(G^{\ast }\right)-D\left(G\right)\right)\bar{x}+{\bar{x}}^{\text{T}}\left(A\left(G^{\ast }\right)-A\left(G\right)\right)\bar{x}\\ =s\left({\bar{x}}_u^2-{\bar{x}}_v^2\right)+2\left({\bar{x}}_u-{\bar{x}}_v\right){\displaystyle \underset{i=1}{\overset{s}{\sum }}{\bar{x}}_{v_i}}\\ =\left({\bar{x}}_u-{\bar{x}}_v\right)\left(s\left({\bar{x}}_v+{\bar{x}}_u\right)+2{\displaystyle \underset{i=1}{\overset{s}{\sum }}{\bar{x}}_{v_i}}\right)\le 0\end{array}$

从而我们可以得到

$q\left(\bar{G}\right)={\bar{x}}^{\text{T}}Q\left(\bar{G}\right)\bar{x}\le {\bar{x}}^{\text{T}}Q\left(\overline{G^{\ast }}\right)\bar{x}\le \underset{\Vert y\Vert =1}{\max }{\bar{y}}^{\text{T}}\left(Q\left(\overline{G^{\ast }}\right)\right)\bar{y}=q\left(\overline{G^{\ast }}\right)$ (1)

如果 $q\left(\bar{G}\right)=q\left(\overline{G^{\ast }}\right)$ ，那么由(1)式可得 $q\left(\overline{G^{\ast }}\right)={\bar{x}}^{\text{T}}Q\left(\overline{G^{\ast }}\right)\bar{x}={\bar{x}}^{\text{T}}Q\left(\bar{G}\right)\bar{x}=q\left(\bar{G}\right)$ 。从而有 $Q\left(\overline{G^{\ast }}\right)\bar{x}=q\left(\overline{G^{\ast }}\right)\bar{x}$ 和 $Q\left(\bar{G}\right)\bar{x}=q\left(\bar{G}\right)\bar{x}$ 成立，进而有 $q\left(\bar{G}\right){\bar{x}}_v={\left(Q\left(\bar{G}\right)\bar{x}\right)}_v=d_{\bar{G}}\left(v\right)+{\displaystyle {\sum }_{v_i\in N_{\bar{G}}\left(v\right)}{\bar{x}}_{v_i}}$ 和 $q\left(\overline{G^{\ast }}\right){\bar{x}}_v={\displaystyle {\sum }_{v_i\in N_{\overline{G^{\ast }}}\left(v\right)}{\bar{x}}_{v_i}}=d_{\overline{G^{\ast }}}\left(v\right)+{\displaystyle {\sum }_{v_i\in N_{\bar{G}}\left(v\right)}{\bar{x}}_{v_i}}+{\displaystyle {\sum }_{i=1}^s{\bar{x}}_{v_i}}$ 。因为 $q\left(\bar{G}\right)=q\left(\overline{G^{\ast }}\right)$ ，所以 ${\displaystyle {\sum }_{i=1}^s{\bar{x}}_{v_i}}<0$ 。这与 $\bar{x}$ 是正向量矛盾，因此在这个定理中 $q\left(\bar{G}\right)$ 严格小于 $q\left(\overline{G^{\ast }}\right)$ 。□

引理2.2设图G和 $\bar{G}$ 都是连通的，uv是图G的一条非悬挂的割边，图G压缩边uv为一个点w并给w带一条悬挂边得到的图形记作 $G^{\ast }$ ，如图1所示。则有 $q\left(\bar{G}\right)<q\left(\overline{G^{\ast }}\right)$ 成立。

Figure 1. G and G^*

图1. G和G^*

证明：令 $G_1=G-{\displaystyle {\sum }_{z\in N_G\left(v\right)\backslash \left\{u\right\}}vz}+{\displaystyle {\sum }_{z\in N_G\left(v\right)\backslash \left\{u\right\}}uz}$ $G_2=G-{\displaystyle {\sum }_{z\in N_G\left(u\right)\backslash \left\{v\right\}}uz}+{\displaystyle {\sum }_{z\in N_G\left(u\right)\backslash \left\{v\right\}}vz}$ 。则容易看出 $G_1$ 和 $G_2$ 都和 $G^{\ast }$ 同构。因此无论是 ${\bar{x}}_v\left(G\right)\ge {\bar{x}}_u\left(G\right)$ 还是 ${\bar{x}}_u\left(G\right)\ge {\bar{x}}_v\left(G\right)$ ，由引理2.1我们都可以得到 $\mu \left(\bar{G}\right)<\mu \left(\overline{G^{\ast }}\right)$ 。□

假设u是图G的一个点， $T_l$ 是以v为根节点的一个l个点的树。我们将图G的u点和图 $T_l$ 的v点粘接成一个点得到的图形记作 $Guv{T}_l$ 。在整篇文章中我们用 $K_{1,l-1}$ 来表示以w为根节点的l个点的星图。

由引理2.2容易得到下面的引理。

引理2.3若图G， $T_l$ 和 $K_{1,l-1}$ 如上所定义，则 $q\left(\overline{Guv{T}_l}\right)\le q\left(\overline{Guw{K}_{1,l-1}}\right)$ ，其中等号成立的充分必要条件是 $Guv{T}_l\cong Guw{K}_{1,l-1}$ 。

3. 单圈图的补图的无符号拉普拉斯谱半径

引理3.1设图G是一个n个点的单圈图，点u是图G所包含的圈 $C_l$ 上的一个点。如果 $3\le l\le n$ ，那么 $q\left(\bar{G}\right)\le q\left(\overline{C_{l}uw{K}_{1,n-l}}\right)$ ；并且只有在 $G\cong C_{l}uw{K}_{1,n-l}$ 时，等号才成立。

证明：假设 $T_i$ 是以图G所含的圈 $C_l$ 上的点 $v_i$ 为根节点的树，其中 $1\le i\le l$ 。令

$G_1=G-{\displaystyle \underset{1\le i\le l}{\sum }E\left(T_i\right)}+{\displaystyle \underset{1\le i\le l}{\sum }{\displaystyle \underset{z\in V\left(T_i\right)}{\sum }{v}_{i}z}}$

由引理2.3有 $q\left(\bar{G}\right)\le q\left(\overline{G_1}\right)$ ，当且仅当 $G\cong G_1$ 时等号成立。

假设 $S_1$ 和 $S_2$ 是图 $G_1$ 的两个星子图，它们分别以 $C_l$ 上的点 $u_1$ 和 $u_2$ 为根节点。

如果 ${\bar{x}}_{u_1}\ge {\bar{x}}_{u_2}$ ，令

$G_2=G_1-{\displaystyle \underset{z\in N_{S_1}\left(u_1\right)}{\sum }{u}_{1}z}+{\displaystyle \underset{z\in N_{S_1}\left(u_1\right)}{\sum }{u}_{2}z}$

如果 ${\bar{x}}_{u_1}\le {\bar{x}}_{u_2}$ ，令

$G_2=G_1-{\displaystyle \underset{z\in N_{S_2}\left(u_2\right)}{\sum }{u}_{2}z}+{\displaystyle \underset{z\in N_{S_2}\left(u_2\right)}{\sum }{u}_{1}z}$

继续上述过程我们可以得到一个与 $C_{l}uw{K}_{1,n-l}$ 同构的单圈图。由引理2.1可得 $q\left(\bar{G}\right)\le q\left(\overline{C_{l}uw{K}_{1,n-l}}\right)$ ，当且仅当 $G\cong C_{l}uw{K}_{1,n-l}$ 时等号成立。□

引理3.2如果 $4\le l\le n$ ，则有 $q\left(\overline{C_{l}uw{K}_{1,n-l}}\right)<q\left(\overline{C_{l-1}uw{K}_{1,n-l+1}}\right)$ 。

证明：假设 $wv$ ， $w^{\prime }w$ 和 $v{v}^{\prime }$ 是 $C_l$ 上的三条边。

如果 $x_w\left(\overline{C_{l}uw{K}_{1,n-l}}\right)\ge x_v\left(\overline{C_{l}uw{K}_{1,n-l}}\right)$ ，则令

$G_1=C_{l}uw{K}_{1,n-l}-{\displaystyle \underset{z\in N_{K_{1,n-l}}\left(w\right)}{\sum }wz}-w^{\prime }w+{\displaystyle \underset{z\in N_{K_{1,n-l}}\left(w\right)}{\sum }vz}+w^{\prime }v$

如果 $x_v\left(\overline{C_{l}uw{K}_{1,n-l}}\right)\ge x_w\left(\overline{C_{l}uw{K}_{1,n-l}}\right)$ ，令

$G_2=C_{l}uw{K}_{1,n-l}-v{v}^{\prime }+w{v}^{\prime }$

显然 $G_1$ 和 $G_2$ 都与 $C_{l-1}uw{K}_{1,n-l+1}$ 同构。由引理2.1我们可以得到 $q\left(\overline{C_{l}uw{K}_{1,n-l}}\right)<q\left(\overline{C_{l-1}uw{K}_{1,n-l+1}}\right)$ 。□

根据引理3.1和3.2我们可以得到下面的定理。

定理3.3如果G是一个含有n个点的单圈图，那么 $q\left(\bar{G}\right)\le q\left(\overline{C_{3}uw{K}_{1,n-3}}\right)$ ，当且仅当 $G\cong C_{3}uw{K}_{1,n-3}$ 时等号成立。

4. 双圈图的补图的无符号拉普拉斯谱半径

边数等于点数加一的连通图是双圈图。令 $C_n$ 和 $P_n$ 分别表示n个点的圈和路，我们定义图 $b\left(p,l,q\right)$ 是由两个点不交的圈 $C_p$ ， $C_q$ 和一条路 $P_l$ 组成的图形，其中 $P_l$ 的两个端点分别和 $C_p$ ， $C_q$ 有一个公共点，特别的，当 $C_p$ 和 $C_q$ 有唯一的公共点时，我们记这个图形为 $b\left(p,0,q\right)$ 。定义图 $\theta \left(p,l,q\right)$ 为给定两个点中间连接有三条路 $P_{p+1}$ ， $P_{l+1}$ 和 $P_{q+1}$ ，其中这三条路两两之间除了两个给定的点外是没有公共点的。我们把 $b\left(p,l,q\right)$ 和 $b\left(p,0,q\right)$ 粘上一些树构成的图形记作 $B_n$ ，把 $\theta \left(p,l,q\right)$ 粘上一些树构成的图形记作 $\Theta \left(p,l,q\right)$ 。显然，所有n个点的双圈图由 $B_n$ 和 ${\Theta }_n$ 组成。

定理4.1设图 $G\in B_n$ ，点u是图 $b\left(3,0,3\right)$ 的4度点。则 $q\left(\bar{G}\right)\le q\left(\overline{b\left(3,0,3\right)uw{K}_{1,n-5}}\right)$ ，当且仅当 $G\cong b\left(3,0,3\right)uw{K}_{1,n-5}$ 时等号成立。

证明：假设图G是由 $b\left(p,l,q\right)$ 粘上一些树组成的图形。我们逐次压缩路 $P_{l+1}$ 上相邻的两点为一个点并在该点上添加一条悬挂边，直到我们得到一个在 $b\left(p,0,q\right)$ 上带有一些树的双圈图，记作 $G_1$ 。由引理2.2可得 $q\left(\bar{G}\right)\le q\left(\overline{G_1}\right)$ ，当且仅当 $G\cong G_1$ 时等号成立。

假设 $T_1$ 和 $T_2$ 是图 $G_1$ 的两个树子图，它们分别以 $b\left(p,0,q\right)$ 上的 $u_1$ 和 $u_2$ 点为根节点。

如果 $x_{u_1}\left(\overline{G_1}\right)\ge x_{u_2}\left(\overline{G_1}\right)$ ，令

$G_2=G_1-{\displaystyle \underset{z\in N_{T_1}\left(u_1\right)}{\sum }{u}_{1}z}+{\displaystyle \underset{z\in N_{T_1}\left(u_1\right)}{\sum }{u}_{2}z}$

如果 $x_{u_1}\left(\overline{G_1}\right)\le x_{u_2}\left(\overline{G_1}\right)$ ，令

$G_2=G_1-{\displaystyle \underset{z\in N_{T_2}\left(u_2\right)}{\sum }{u}_{2}z}+{\displaystyle \underset{z\in N_{T_2}\left(u_2\right)}{\sum }{u}_{1}z}$

继续上述过程我们可以得到一个在 $b\left(p,0,q\right)$ 上的y点处带有一个树的双圈图，记作 $G_3$ ，由引理2.1有 $q\left(\overline{G_1}\right)\le q\left(\overline{G_3}\right)$ ，当且仅当 $G_1\cong G_3$ 时等号成立。由引理2.3可以得到 $q\left(\overline{G_3}\right)\le q\left(\overline{b\left(p,0,q\right)yw{K}_{1,n-p-q+1}}\right)$ ，当且仅当 $G_3\cong b\left(p,0,q\right)yw{K}_{1,n-p-q+1}$ 时等号成立。

令 $H=b\left(p,0,q\right)yw{K}_{1,n-p-q+1}$ ，不失一般性假设 $p>3$ ，我们来考虑图H的圈子图 $C_p$ 上的边 $u_3{u}_4$ 。

如果 $x_{u_3}\left(\bar{H}\right)\ge x_{u_4}\left(\bar{H}\right)$ ，令

$G_4=H-{\displaystyle \underset{z\in N_H\left(u_3\right)\backslash \left\{u_4\right\}}{\sum }{u}_{3}z}+{\displaystyle \underset{z\in N_H\left(u_3\right)\backslash \left\{u_4\right\}}{\sum }{u}_{4}z}$

如果 $x_{u_3}\left(\bar{H}\right)\le x_{u_4}\left(\bar{H}\right)$ ，令

$G_4=H-{\displaystyle \underset{z\in N_H\left(u_4\right)\backslash \left\{u_3\right\}}{\sum }{u}_{4}z}+{\displaystyle \underset{z\in N_H\left(u_4\right)\backslash \left\{u_3\right\}}{\sum }{u}_{3}z}$

显然 $G_4$ 是双圈图 $b\left(p-1,0,q\right)$ 上带有一些悬挂边构成的图形。继续上述过程我们可以得到图 $G_5$ ，它是由 $b\left(3,0,3\right)$ 带一些悬挂边构成的图形。由引理2.1有 $q\left(\bar{H}\right)\le q\left(\overline{G_5}\right)$ 成立，当且仅当 $H\cong G_5$ 时等号成立。

假设图 $G_5$ 的两个星子图 $S_5$ 和 $S_6$ 分别以 $b\left(3,0,3\right)$ 上的点 $u_5$ 和 $u_6$ 为根节点。

如果 $x_{u_5}\left(\overline{G_5}\right)\ge x_{u_6}\left(\overline{G_5}\right)$ ，令

$G_6=G_5-{\displaystyle \underset{z\in N_{S_5}\left(u_5\right)}{\sum }{u}_{5}z}+{\displaystyle \underset{z\in N_{S_5}\left(u_5\right)}{\sum }{u}_{6}z}$

如果 $x_{u_5}\left(\overline{G_5}\right)\le x_{u_6}\left(\overline{G_5}\right)$ ，令

$G_6=G_5-{\displaystyle \underset{z\in N_{S_6}\left(u_6\right)}{\sum }{u}_{6}z}+{\displaystyle \underset{z\in N_{S_6}\left(u_6\right)}{\sum }{u}_{5}z}$

继续上述过程我们可以由 $G_5$ 得到一个与 $b\left(3,0,3\right)y^{\prime }w{K}_{1,n-5}$ 同构的双圈图。由引理2.1我们有 $q\left(\overline{G_5}\right)\le q\left(\overline{b\left(3,0,3\right)y^{\prime }w{K}_{1,n-5}}\right)$ ，当且仅当 $G_5\cong b\left(3,0,3\right)y^{\prime }w{K}_{1,n-5}$ 时等号成立。

令 $H^{\prime }=b\left(3,0,3\right)y^{\prime }w{K}_{1,n-5}$ ，若 $d_b\left(3,0,3\right)\left(y^{\prime }\right)=2$ ，则 $H^{\prime }$ 如图2(a)。

(a) (b)

Figure 2. (a) $b\left(3,0,3\right)y^{\prime }w{K}_{1,n-5}$ ; (b) $\theta \left(2,1,2\right)y^{\prime }w{K}_{1,n-4}$

图2. (a) $b\left(3,0,3\right)y^{\prime }w{K}_{1,n-5}$ ; (b) $\theta \left(2,1,2\right)y^{\prime }w{K}_{1,n-4}$

如果 $x_{y^{\prime }}\left(\overline{H^{\prime }}\right)\ge x_u\left(\overline{H^{\prime }}\right)$ ，令

$G_7=H^{\prime }-{\displaystyle \underset{1\le i\le n-5}{\sum }{y}^{\prime }{v}_i}+{\displaystyle \underset{1\le i\le n-5}{\sum }u{v}_i}$

如果 $x_{y^{\prime }}\left(\overline{H^{\prime }}\right)\le x_u\left(\overline{H^{\prime }}\right)$ ，令

$G_7=H^{\prime }-u{y}_1-u{y}_2+y^{\prime }{y}_1+y^{\prime }{y}_2$

显然 $G_7\cong b\left(3,0,3\right)uw{K}_{1,n-5}$ ，由引理2.1有 $q\left(\overline{H^{\prime }}\right)\le q\left(\overline{G_7}\right)$ 。□

定理4.2设图 $G\in {\Theta }_n$ ，u是图 $\theta \left(2,1,2\right)$ 上的3度点。则 $q\left(\bar{G}\right)\le q\left(\overline{\theta \left(2,1,2\right)uw{K}_{1,n-4}}\right)$ ，当且仅当 $G\cong \theta \left(2,1,2\right)uw{K}_{1,n-4}$ 时等号成立。

证明：假设 $T_1$ 和 $T_2$ 是图G的两个树子图，它们分别以 $\theta \left(p,l,q\right)$ 上的点 $u_1$ 和 $u_2$ 为根节点。

如果 $x_{u_1}\left(\bar{G}\right)\ge x_{u_2}\left(\bar{G}\right)$ ，令

$G_1=G-{\displaystyle \underset{z\in N_{T_1}\left(u_1\right)}{\sum }{u}_{1}z}+{\displaystyle \underset{z\in N_{T_1}\left(u_1\right)}{\sum }{u}_{2}z}$

如果 $x_{u_1}\left(\bar{G}\right)\le x_{u_2}\left(\bar{G}\right)$ ，令

$G_1=G-{\displaystyle \underset{z\in N_{T_2}\left(u_2\right)}{\sum }{u}_{2}z}+{\displaystyle \underset{z\in N_{T_2}\left(u_2\right)}{\sum }{u}_{1}z}$

继续上述过程直到该双圈图只含有一个树子图，它以 $\theta \left(p,l,q\right)$ 上的点y为根节点，我们把这个双圈图记作 $G_2$ 。由引理2.1有 $q\left(\bar{G}\right)\le q\left(\overline{G_2}\right)$ ，当且仅当 $G\cong G_2$ 时等号成立。由引理2.3有 $q\left(\overline{G_2}\right)\le q\left(\overline{\theta \left(p,l,q\right)yw{K}_{1,n-p-l-q+1}}\right)$ ，当且仅当 $G_2\cong \theta \left(p,l,q\right)yw{K}_{1,n-p-l-q+1}$ 时等号成立。

令 $H=\theta \left(p,l,q\right)yw{K}_{1,n-p-l-q+1}$ 。如果p，l和q中有一个大于等于3我们会得到比图H的补图的无符号拉普拉斯谱更大的图。不失一般性，我们假设 $l\ge 3$ 。我们考虑图H的子图 $P_l$ 上的一条边 $u_3{u}_4$ 。

如果 $x_{u_3}\left(\bar{H}\right)\ge x_{u_4}\left(\bar{H}\right)$ ，令

$G_3=H-{\displaystyle \underset{z\in N_H\left(u_3\right)\backslash \left\{u_4\right\}}{\sum }{u}_{3}z}+{\displaystyle \underset{z\in N_H\left(u_3\right)\backslash \left\{u_4\right\}}{\sum }{u}_{4}z}$

如果 $x_{u_3}\left(\bar{H}\right)\le x_{u_4}\left(\bar{H}\right)$ ，令

$G_3=H-{\displaystyle \underset{z\in N_H\left(u_4\right)\backslash \left\{u_3\right\}}{\sum }{u}_{4}z}+{\displaystyle \underset{z\in N_H\left(u_4\right)\backslash \left\{u_3\right\}}{\sum }{u}_{3}z}$

显然 $G_3\in {\theta }_n$ ，它是在 $\theta \left(p,l-1,q\right)$ 上粘一些悬挂边得到的图形。继续上述过程我们可以得到一个双圈图 $G_4$ ，它是由 $\theta \left(2,1,2\right)$ 添上一些悬挂边构成的图形。由引理2.1有 $q\left(\bar{H}\right)\le q\left(\overline{G_4}\right)$ ，当且仅当 $H\cong G_4$ 时等号成立。

假设 $S_5$ 和 $S_6$ 是图 $G_4$ 的两个星子图，它们分别以 $\theta \left(2,1,2\right)$ 上的 $u_5$ 和 $u_6$ 点为根节点。

如果 $x_{u_5}\left(\overline{G_4}\right)\ge x_{u_6}\left(\overline{G_4}\right)$ ，令

$G_5=G_4-{\displaystyle \underset{z\in N_{S_5}\left(u_5\right)}{\sum }{u}_{5}z}+{\displaystyle \underset{z\in N_{S_5}\left(u_5\right)}{\sum }{u}_{6}z}$

如果 $x_{u_5}\left(\overline{G_4}\right)\le x_{u_6}\left(\overline{G_4}\right)$ ，令

$G_5=G_4-{\displaystyle \underset{z\in N_{S_6}\left(u_6\right)}{\sum }{u}_{6}z}+{\displaystyle \underset{z\in N_{S_6}\left(u_6\right)}{\sum }{u}_{5}z}$

继续上述过程我们可以得到一个与 $\theta \left(2,1,2\right)y^{\prime }w{K}_{1,n-4}$ 同构的双圈图。由引理2.1有 $q\left(\overline{G_4}\right)\le q\left(\overline{\theta \left(2,1,2\right)y^{\prime }w{K}_{1,n-4}}\right)$ ，当且仅当 $G_4\cong \theta \left(2,1,2\right)y^{\prime }w{K}_{1,n-4}$ 时等号成立。

令 $H^{\prime }=\theta \left(2,1,2\right)y^{\prime }w{K}_{1,n-4}$ ，若 $d_{\theta }\left(2,1,2\right)\left(y^{\prime }\right)=2$ ，则 $H^{\prime }$ 如图2(b)。

如果 $x_{y^{\prime }}\left(\overline{H^{\prime }}\right)\ge x_u\left(\overline{H^{\prime }}\right)$ ，令

$G_5=H^{\prime }-{\displaystyle \underset{1\le i\le n-4}{\sum }{y}^{\prime }{v}_i}+{\displaystyle \underset{1\le i\le n-4}{\sum }u{v}_i}$

如果 $x_{y^{\prime }}\left(\overline{H^{\prime }}\right)\le x_u\left(\overline{H^{\prime }}\right)$ ，令

$G_5=H^{\prime }-u{y}_2+y^{\prime }{y}_2$

显然 $G_5\cong \theta \left(2,1,2\right)uw{K}_{1,n-4}$ ，由引理2.1有 $q\left(\overline{H^{\prime }}\right)\le q\left(\overline{G_5}\right)$ ，当且仅当 $H^{\prime }\cong G_5$ 时等号成立。□

引理4.3 [3] 若G是一个n个点的图，则有 $\min \left\{d_i+d_j\right\}\le q\left(G\right)\le \max \left\{d_i+d_j\right\}$ ，其中 $\left(i,j\right)$ 取遍图G的所有邻接点对。若图G是连通的，那么等号成立的充分必要条件是图G是一个正则图或者是个半正则的二部图。

定理4.4设图G是一个n个点的连通双圈图，那么 $q\left(\bar{G}\right)\le q\left(\overline{\theta \left(2,1,2\right)uw{K}_{1,n-4}}\right)$ ，当且仅当 $G\cong \theta \left(2,1,2\right)uw{K}_{1,n-4}$ 时等号成立，其中 $d_{\theta }\left(2,1,2\right)\left(u\right)=3$ 。

证明：令 $b\left(3,0,3\right)$ 的4度点为v，由定理4.1和定理4.2知，我们只需证明

$q\left(\overline{b\left(3,0,3\right)vw{K}_{1,n-5}}\right)<q\left(\overline{\theta \left(2,1,2\right)uw{K}_{1,n-4}}\right)$

令 $H_1=b\left(3,0,3\right)vw{K}_{1,n-5}$ ， $H_2=\theta \left(2,1,2\right)uw{K}_{1,n-4}$ 我们有

$\begin{array}{c}P\left(\overline{H_1};\lambda \right)=\left|I\lambda -Q\left(\overline{H_1}\right)\right|\\ =\lambda {\left(\lambda -n+3\right)}^{n-4}\left({\lambda }^3+\left(14-4n\right){\lambda }^2+\left(5n^2-38n+73\right)\lambda -\left(2n^3-24n^2+98n-140\right)\right)\end{array}$

$\begin{array}{c}P\left(\overline{H_2};\lambda \right)=\left|I\lambda -Q\left(\overline{H_2}\right)\right|\\ =\lambda {\left(\lambda -n+3\right)}^{n-4}\left({\lambda }^3+\left(14-4n\right){\lambda }^2+\left(5n^2-38n+72\right)\lambda -\left(2n^3-24n^2+96n-128\right)\right)\end{array}$

显然当 $\lambda \ge 2n-6$ 时， $P\left(\overline{H_1};\lambda \right)-P\left(\overline{H_2};\lambda \right)=\lambda {\left(\lambda -n+3\right)}^{n-4}\left(\lambda -2\left(n-6\right)\right)>0$ 成立。由引理4.3有 $2n-6\le q\left(\overline{H_1}\right)$ ， $q\left(\overline{H_2}\right)\le 2n-4$ ，所以有

$q\left(\overline{b\left(3,0,3\right)vw{K}_{1,n-5}}\right)<q\left(\overline{\theta \left(2,1,2\right)uw{K}_{1,n-4}}\right)$ 。□

基金项目

新疆自治区研究生创新项目(XJ2021G253)。

NOTES

^*通讯作者。