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

Distance Signless Laplacian Spectral Radius of the Complements of Bicyclic Graphs

摘要: 设G是简单连通图，$D^Q\left(G\right)=Tr\left(G\right)+D\left(G\right)$ 为图G的距离无符号拉普拉斯矩阵，其中$Tr\left(G\right)$ 和$D\left(G\right)$ 分别是图G的点传递对角矩阵和距离矩阵。本文在n阶双圈图补图中确定了距离无符号拉普拉斯谱半径最大时所落在的图类集合。

Abstract: Let G be a simple connected graph, and $D^Q\left(G\right)=Tr\left(G\right)+D\left(G\right)$ be the distance signless Laplacian matrix of graph G, where $Tr\left(G\right)$ and $D\left(G\right)$ are diagonal matrix with vertex transmissions of G and distance matrix of G, respectively. This article determines the set of graph classes that fall at the maximum distance from signless Laplacian spectral radius in the complements of bicyclic graphs with n-order.

1. 引言

设$G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个具有n个顶点和m条边的简单连通图，图$G$ 的补图记为$\overline{G}$ 。图$G$ 的距离矩阵记为$D\left(G\right)={\left(d_{i,j}\right)}_{n\times n}$ ，其中$d_{i,j}=d_G\left(v_i,v_j\right)$ 表示两点$v_i$ 和$v_j$ 之间最短路的长度，即$v_i$ 和$v_j$ 间的距离。用$\text{diam}\left(G\right)=\max \left\{d_G\left(v_i,v_j\right)|v_i,v_j\in V\left(G\right)\right\}$ 表示图$G$ 的直径。图$G$ 中某个顶点$v_i$ 的点传递$Tr\left(v_i\right)$ 是点$v_i$ 到其它所有点的距离之和，即$Tr\left(v_i\right)={\displaystyle \sum _{v_j\in V(G)}{d}_G}\left(v_i,v_j\right)$ 。设矩阵$Tr\left(G\right)=\text{diag}\left(Tr\left(v_1\right),Tr\left(v_2\right),\cdots ,Tr\left(v_n\right)\right)$ 是图$G$ 的点传递对角矩阵，$G$ 的距离无符号拉普拉斯矩阵定义为：

$D^Q\left(G\right)=Tr\left(G\right)+D\left(G\right).$

$D^Q\left(G\right)$ 是一个不可约、非负、实对称的正定矩阵。$G$ 的最大距离无符号拉普拉斯特征值被称为$G$ 的距离无符号拉普拉斯谱半径，记为$\mu \left(G\right)$ 。图的特征值性质反映了其矩阵所对应的性质，研究图的特征值具有重要的理论和实际意义。其中，从图的谱半径出发去探索相应的图结构，可以更加深刻地对图的离散结构的内在关系进行刻画。因此，谱半径是图谱理论不可或缺的工具。

相较邻接矩阵而言，拉普拉斯矩阵和无符号拉普拉斯矩阵的对角线直接反映了图各个顶点的度大小。作为图的拉普拉斯矩阵和无符号拉普拉斯矩阵的推广，结合图的距离矩阵，Aouchiche和Hansen于2013年在文献[1]中首次提出了连通图距离无符号拉普拉斯矩阵的概念。对距离矩阵而言，距离无符号拉普拉斯矩阵的对角线上元素直接反映了图的各个顶点的点传递。距离无符号拉普拉斯矩阵展示的图的结构信息比距离矩阵更加直接、全面。

距离无符号拉普拉斯矩阵吸引了许多学者对其进行研究。Li等在文献[2]中给出了连通图的距离无符号拉普拉斯谱半径关于色数的下界，Lin和Lu在文献[3]中给出了连通图的距离无符号拉普拉斯谱半径关于团数的上下界，Bapat等在文献[4]中确定了所有单圈图中距离无符号拉普拉斯谱半径是最大时的极图。

图$G$ 的补图$\overline{G}$ 是$V\left(G\right)=V\left(\overline{G}\right)$ 且两个(不同的)邻点在$\overline{G}$ 中相邻当且仅当在$G$ 中不相邻的图。有些图类其本身结构复杂，但它们的补图的结构却相对简单。因此，一些学者从补图的结构出发来研究图的距离拉普拉斯及距离无符号拉普拉斯谱。Xue等在文献[5]中证明了路和圈的补图可以由它们的距离(无符号)拉普拉斯谱确定。Li等在文献[6]中刻画了单圈图补图的距离无符号拉普拉斯谱半径取得最大值的唯一图。

边数等于顶点数加一的连通图则为双圈图。相对来说，研究双圈图补图的文章还不太多。Li和Liang在文献[7]中刻画了在双圈图补图中匹配数为极值k的k匹配的图。Chen和Wang在文献[8]中扩展了n阶双圈图的补图中$A_{\alpha }$ 谱半径的最大排序。本文在n阶双圈图补图中确定了距离无符号拉普拉斯谱半径最大时所落在的图类集合。

2. 准备工作

令$J_{\text{n}}$ 为全1的$n$ 阶矩阵，$I_{\text{n}}$ 为n阶单位矩阵。

引理2.1 [9]设图$G$ 为n阶连通图，$\text{diam}\left(G\right)\ge 3$ ，则有：

1) 若$\text{diam}\left(G\right)>3$ ，则$D\left(\overline{G}\right)=J_{\text{n}}-I_{\text{n}}+A\left(G\right)$。

2) 若$\text{diam}\left(G\right)=3$ ，则$D\left(\overline{G}\right)\ge J_{\text{n}}-I_{\text{n}}+A\left(G\right)$。

若连通图$G$ 满足$\left|E\left(G\right)\right|=\left|V\left(G\right)\right|+1$ ，则称图$G$ 为双圈图。设$B_n$ 是$n$ 阶双圈图的集合，令$C_n$ 、$P_n$ 、$K_{1,n-1}$ 、$T_{p,q}\left(p+q=n-2\right)$ 分别表示$n$ 阶圈、路、星和双星。

设h、l、k是任意非负整数且$h\ge k\ge 3$ 。设$C_h$ 和$C_k$ 分别是包含点u和点v的两个不相交的圈，$P_{l+1}$ 是点u和点v之间的一条路，令$R_{h,l,k}$ 是由圈$C_h$ 的一个顶点和$C_k$ 的一个顶点通过路$P_{l+1}$ 连接得到的n阶双圈图的集合，如图1所示。本文用${\Re }_n$ 表示在图$R_{h,l,k}$ 的点上粘上一些悬挂树的n阶图的集合。设$P$ 、$P\text{'}$ 是顶点u和v之间的两条不同路，若$V\left(P\cap P^{\prime }\right)=\left\{u,v\right\}$ 且$E\left(P\right)\cap E\left(P^{\prime }\right)=\varnothing$ ，则称$P$ 、$P^{\prime }$ 是连接顶点u和v的两条内部点不相交的路。

Figure 1. Panel $R_{h,l,k}$

图1. 图$R_{h,l,k}$

设h’、l’、k’是任意正整数，令${\theta }_{h^{\prime },l^{\prime },k^{\prime }}$ 是由三条内部点不相交的路$P_{h^{\prime }+1}=u{u}_1\cdots u_{h^{\prime }-1}v$ 、$P_{k^{\prime }+1}=u{u^{\prime }}_1\cdots {u^{\prime }}_{k^{\prime }-1}v$ 和$P_{l^{\prime }+1}=u{u^{″}}_1\cdots {u^{″}}_{l^{\prime }-1}v$ 组成的具有公共端点u和v的n阶双圈图的集合，如图2所示。用${\Phi }_{\text{n}}$ 表示在图${\theta }_{h^{\prime },l^{\prime },k^{\prime }}$ 的点上粘上一些悬挂树的n阶图的集合。显然${{\rm B}}_n={\Re }_n+{\Phi }_n$ 。

Figure 2. Panel ${\theta }_{h^{\prime },l^{\prime },k^{\prime }}$

图2. 图${\theta }_{h^{\prime },l^{\prime },k^{\prime }}$

设p、q是任意正整数，图$R_{h,l,k}u\left(p,q\right)$ 是在图$R_{h,l,k}$ 的u点上粘上双星$T_{p-1,q}$ ，且$d_{T_{p-1，q}}\left(u\right)=p$ ，$d_{T_{p-1，q}}\left(u^{\prime }\right)=q+1$ 。图$R_{h,l,k}uv\left(p,q\right)$ 是在图$R_{h,l,k}$ 的u点粘上星$K_{1,p}$ 且在点v上粘接星$K_{1,q}$ 得到的图，且$d_{K_{1,p}}\left(u\right)=p$ ，$d_{K_{1,p}}\left(v\right)=q$ 。设m为任意正整数，图$R_{h,l,k}u\left(m\right)$ 是在图$R_{h,l,k}$ 的u点上粘接星$K_{1,m}$ 得到的图，且$d_{K_{1,m}}\left(u\right)=m$ 。对图${\theta }_{h^{\prime },l^{\prime },k^{\prime }}u\left(p,q\right)$ 、${\theta }_{h^{\prime },l^{\prime },k^{\prime }}uv\left(p,q\right)$ 、${\theta }_{h^{\prime },l^{\prime },k^{\prime }}u\left(m\right)$ 也是一样定义。

本文主要研究n阶双圈图补图的距离无符号拉普拉斯谱半径，因此在${{\rm B}}_n$ 中不考虑图$R_{3,0,3}$ 、$R_{3,0,3}u\left(n-5\right)$ 、${\theta }_{2,1,2}$ 、${\theta }_{2\text{,}2,2}$ 、${\theta }_{2,1,2}u\left(n-4\right)$ 。由引理2.1可知，若$\text{diam}\left(G\right)\ge 4$ ，则$D\left(\overline{G}\right)=J_n-I_n+A\left(G\right)$ ，否则$D\left(\overline{G}\right)\ge J_n-I_n+A\left(G\right)$ 。令$S=\left\{G|G\in {\rm B},n\ge 7,\text{diam}\left(G\right)=3，D\left(\overline{G}\right)>J_n-I_n+A\left(G\right)\right\}$。则集合$S$ 中共有21类可能的图，如图3所示，依次为$R_{3,0,3}u\left(p,q\right)$ 、$R_{3,0,3}{u}_1\left(p,q\right)$ 、$R_{3,0,3}u{u}_1\left(p,q\right)$ ；$R_{3,0,4}u\left(n-6\right)$ 、$R_{3,0,4}{u^{\prime }}_1\left(n-6\right)$ 、$R_{3,0,4}u{u^{\prime }}_1\left(p,q\right)$ ；$R_{3,1,3}u\left(n-6\right)$ 、$R_{3,1,3}uv\left(p,q\right)$ 、${\theta }_{2,1,2}u\left(p,q\right)$ ；${\theta }_{2,1,2}{u}_1\left(n-4\right)$ 、${\theta }_{2,1,2}u{u}_1\left(p,q\right)$ 、${\theta }_{2,1,2}uv\left(p,q\right)$ ；${\theta }_{3,1,2}u\left(n-5\right)$ 、${\theta }_{3,1,2}{u}_1\left(n-5\right)$ 、${\theta }_{3,1,2}u{u}_1\left(p,q\right)$ ；${\theta }_{3,1,2}uv\left(p,q\right)$ 、${\theta }_{3,1,3}u\left(n-6\right)$ 、${\theta }_{3,1,3}uv\left(p,q\right)$ ；${\theta }_{2,2,2}u\left(n-5\right)$ 、${\theta }_{2,2,2}{u}_1\left(n-5\right)$ 、${\theta }_{2,2,2}u{u}_1\left(p,q\right)$ 。

Figure 3. Set S

图3. 集合S

3. 图变换

本节将给出两个增大补图的距离无符号拉普拉斯谱半径的图变换。

图$G$ 中任意顶点$v$ 的邻点集记为$N_G\left(v\right)$ 。若两个图$G$ 和$H$ 同构，则记为$G\cong H$ 。

引理3.1 (变换1) 设图$G$ 是n阶连通图，假设$uv$ 是图$G$ 的一条非悬挂割边。将图$G$ 的$uv$ 收缩到顶点u，并将悬挂点v和u相连所得到的图记作$G_1$ ，如图4所示，则

$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}_1\right).$

Figure 4. Panel $G$ and Panel $G_1$

图4. 图$G$ 和图$G_1$

证明 设$x$ 为关于的Perron向量，不失一般性，假设$x_u\ge x_v$ 。令$S_1=N_G\left(u\right)\backslash \left\{v\right\}$ ，$S_2=N_G\left(v\right)\backslash \left\{u\right\}$ ，对任意$z_1\in S_1$ ，$z_2\in S_2$ ，比较$\overline{G}$ 和${\overline{G}}_1$ ，有

$d_{\overline{G}}\left(u,z_1\right)=2,d_{{\overline{G}}_1}\left(u,z_1\right)\ge 2,$

$d_{\overline{G}}\left(u,z_2\right)=2,d_{{\overline{G}}_1}\left(u,z_2\right)=2,$

$d_{\overline{G}}\left(v,z_2\right)=2,d_{{\overline{G}}_1}\left(v,z_2\right)=1.$

由于$\overline{G}$ 和${\overline{G}}_1$ 中其他顶点对之间的距离相等，那么有

$\begin{array}{c}\mu \left({\overline{G}}_1\right)-\mu \left(\overline{G}\right)\ge x^{\text{T}}{D}^Q\left({\overline{G}}_1\right)x-x^{\text{T}}{D}^Q\left(\overline{G}\right)x\\ =2x_u{\displaystyle \sum _{z_1\in S_1}\left(d_{{\overline{G}}_1}\left(u,z_1\right)-d_{\overline{G}}\left(u,z_1\right)\right)x_{z_1}+2x_u}{\displaystyle \sum _{z_2\in S_2}\left(d_{{\overline{G}}_1}\left(u,z_2\right)-d_{\overline{G}}\left(u,z_2\right)\right)x_{z_2}}\\ +2x_v{\displaystyle \sum _{z_2\in S_2}\left(d_{{\overline{G}}_1}\left(v,z_2\right)-d_{\overline{G}}\left(v,z_2\right)\right)x_{z_2}+x_u{}^2}{\displaystyle \sum _{z_1\in S_1}\left(d_{{\overline{G}}_1}\left(u,z_1\right)-d_{\overline{G}}\left(u,z_1\right)\right)}\\ +x_u{}^2{\displaystyle \sum _{z_2\in S_2}\left(d_{{\overline{G}}_1}\left(u,z_2\right)-d_{\overline{G}}\left(u,z_2\right)\right)}+x_v{}^2{\displaystyle \sum _{z_2\in S_2}\left(d_{{\overline{G}}_1}\left(v,z_2\right)-d_{\overline{G}}\left(v,z_2\right)\right)}\\ =2x_u{\displaystyle \sum _{z_1\in S_1}\left(d_{{\overline{G}}_1}\left(u,z_1\right)-d_{\overline{G}}\left(u,z_1\right)\right)x_{z_1}+}{x}_u{}^2{\displaystyle \sum _{z_1\in S_1}\left(d_{{\overline{G}}_1}\left(u,z_1\right)-d_{\overline{G}}\left(u,z_1\right)\right)}\\ +2\left(x_u-x_v\right){\displaystyle \sum _{z_2\in S_2}{x}_{z_2}}+\left(x_u^2-x_v^2\right)\left|S_2\right|\\ \ge \left(x_u-x_v\right)\left(2{\displaystyle \sum _{z_2\in S_2}{x}_{z_2}}+\left(x_u+x_v\right)\left|S_2\right|\right)\\ \ge 0\end{array}$

若$\mu \left(\overline{G}\right)=\mu \left({\overline{G}}_1\right)$ ，则对于顶点$u$ ，有$0=\mu \left({\overline{G}}_1\right)x_u-\mu \left(\overline{G}\right)x_u={\displaystyle \sum _{z_2\in S_2}{x}_{z_2}}+x_u\left|S_2\right|>0$ ，产生矛盾。因此，当$x_u\ge x_v$ 时，$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}_1\right)$ 。

引理3.2 (变换2) 令图$G\in {{\rm B}}_n\backslash S$ 且$n\ge 7$ ，$u^{\prime }$ 和$v^{\prime }$ 分别为图$G$ 圈上的点，设$x$ 是关于$\mu \left(\overline{G}\right)$ 的Perron向量，设$S_1=\left\{v_1,v_2,\cdots ,v_s\right\}\subset N_G\left(v^{\prime }\right)\backslash N_G\left(u^{\prime }\right)$ 。若$S_1\ne \varnothing$ ，定义图$G_1=G-\left\{v^{\prime }w|w\in S_1\right\}+\left\{u^{\prime }w|w\in S_1\right\}$ 。若图$\overline{G}$ 是连通的且$x_{u^{\prime }}\ge x_{v^{\prime }}$ ，则

$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}_1\right).$

证明 令$S_2=N_G\left(u^{\prime }\right)\backslash \left\{v^{\prime }\right\}$ ，对任意$z_1\in S_2$ ，$z_2\in S_1$ ，比较$\overline{G}$ 和${\overline{G}}_1$ ，有

$d_{\overline{G}}\left(u^{\prime },z_1\right)=2,d_{{\overline{G}}_1}\left(u^{\prime },z_1\right)\ge 2,$

$d_{\overline{G}}\left(u^{\prime },z_2\right)=2,d_{{\overline{G}}_1}\left(u^{\prime },z_2\right)\ge 2,$

$d_{\overline{G}}\left(v^{\prime },z_2\right)=2,d_{{\overline{G}}_1}\left(v^{\prime },z_2\right)=1.$

由于$\overline{G}$ 和${\overline{G}}_1$ 中其他顶点对之间的距离相等，那么有

$\begin{array}{c}\mu \left({\overline{G}}_1\right)-\mu \left(\overline{G}\right)\ge x^{\text{T}}{D}^Q\left({\overline{G}}_1\right)x-x^{\text{T}}{D}^Q\left(\overline{G}\right)x\\ =2x_{u^{\prime }}{\displaystyle \sum _{z_1\in S_2}\left(d_{{\overline{G}}_1}\left(u^{\prime },z_1\right)-d_{\overline{G}}\left(u^{\prime },z_1\right)\right)x_{z_1}+2x_{u^{\prime }}}{\displaystyle \sum _{z_2\in S_1}\left(d_{{\overline{G}}_1}\left(u^{\prime },z_2\right)-d_{\overline{G}}\left(u^{\prime },z_2\right)\right)x_{z_2}}\\ +2x_{v^{\prime }}{\displaystyle \sum _{z_2\in S_1}\left(d_{{\overline{G}}_1}\left(v^{\prime },z_2\right)-d_{\overline{G}}\left(v^{\prime },z_2\right)\right)x_{z_2}+x_{u^{\prime }}^2}{\displaystyle \sum _{z_1\in S_2}\left(d_{{\overline{G}}_1}\left(u^{\prime },z_1\right)-d_{\overline{G}}\left(u^{\prime },z_1\right)\right)}\\ +x_{u^{\prime }}^2{\displaystyle \sum _{z_2\in S_1}\left(d_{{\overline{G}}_1}\left(u^{\prime },z_2\right)-d_{\overline{G}}\left(u^{\prime },z_2\right)\right)}+x_{v^{\prime }}^2{\displaystyle \sum _{z_2\in S_1}\left(d_{{\overline{G}}_1}\left(v^{\prime },z_2\right)-d_{\overline{G}}\left(v^{\prime },z_2\right)\right)}\\ \ge 2x_{u^{\prime }}{\displaystyle \sum _{z_1\in S_2}\left(d_{{\overline{G}}_1}\left(u^{\prime },z_1\right)-d_{\overline{G}}\left(u^{\prime },z_1\right)\right)x_{z_1}+}{x}_{u^{\prime }}^2{\displaystyle \sum _{z_1\in S_2}\left(d_{{\overline{G}}_1}\left(u^{\prime },z_1\right)-d_{\overline{G}}\left(u^{\prime },z_1\right)\right)}\\ +2\left(x_{u^{\prime }}-x_{v^{\prime }}\right){\displaystyle \sum _{z_2\in S_1}{x}_{z_2}}+\left(x_{u^{\prime }}^2-x_{v^{\prime }}^2\right)\left|S_1\right|\\ \ge \left(x_{u^{\prime }}-x_{v^{\prime }}\right)\left(2{\displaystyle \sum _{z_2\in S_1}{x}_{z_2}}+\left(x_{u^{\prime }}+x_{v^{\prime }}\right)\left|S_1\right|\right)\\ \ge 0\end{array}$

若$\mu \left(\overline{G}\right)=\mu \left({\overline{G}}_1\right)$ ，设$x$ 为$D^Q\left({\overline{G}}_1\right)$ 关于$\mu \left({\overline{G}}_1\right)$ 的特征向量，则有

$\begin{array}{c}0=\mu \left({\overline{G}}_1\right)x_{v^{\prime }}-\mu \left(\overline{G}\right)x_{v^{\prime }}\\ ={\displaystyle \sum _{z_2\in S_1}\left(d_{{\overline{G}}_1}\left(v^{\prime },z_2\right)\right)x_{z_2}+x_{v\text{'}}{\displaystyle \sum _{z_2\in S_1}{d}_{{\overline{G}}_1}\left(v^{\prime },z_2\right)-}}{\displaystyle \sum _{z_2\in S_1}\left(d_{\overline{G}}\left(v^{\prime },z_2\right)\right)x_{z_2}}-x_{v^{\prime }}{\displaystyle \sum _{z_2\in S_1}\left(d_{\overline{G}}\left(v^{\prime },z_2\right)\right)}\\ =\left({\displaystyle \sum _{z_2\in S_1}\left(d_{{\overline{G}}_1}\left(v^{\prime },z_2\right)-d_{{\overline{G}}_1}\left(v^{\prime },z_2\right)\right)x_{z_2}}\right)+\left(x_{v^{\prime }}{\displaystyle \sum _{z_2\in S_1}\left(d_{{\overline{G}}_1}\left(v^{\prime },z_2\right)-d_{\overline{G}}\left(v^{\prime },z_2\right)\right)}\right)\\ <0.\end{array}$

产生矛盾。因此，当$x_{u^{\prime }}\ge x_{v^{\prime }}$ 时，$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}_1\right)$ 。

4. 主要结果

引理4.1 令图$G\in {\Re }_{\text{n}}\backslash \left({\Re }_{\text{n}}\cap S\right)$ ，$x$ 是关于$\mu \left(\overline{G}\right)$ 的Perron向量。对于任意正整数$n\ge 7$ 时，一定存在图$G^{\prime }\in {\Phi }_{\text{n}}$ 。若图${\overline{G}}^{\prime }$ 是连通的，则

$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}^{\prime }\right).$

证明 设$C_{\text{h}}$ 、$C_{\text{k}}$ 为图$G$ 的两个点不交的圈，u和v分别是两个圈上的点。连接u和v所得到的路记作$P_{\text{l}+1}$ 。设$u^{\prime }\in V\left(C_h\right)$ ，$v^{\prime }\in V\left(C_k\right)$ 且$u^{\prime }\ne u$ ，$v^{\prime }\ne v$ ，$u^{″}\in N_{C_h}\left(u^{\prime }\right)\backslash \left\{u\right\}$ ，$v^{″}\in N_{C_k}\left(v^{\prime }\right)\backslash \left\{v\right\}$ 。

若$x_{u^{\prime }}\ge x_{v^{\prime }}$ ，去掉圈$C_{\text{k}}$ 上的边$v^{\prime }{v}^{″}$ ，并新加一条边$v^{″}{u}^{\prime }$ ，所得到的图记作$G_1$ ，则$G_1\in {\Phi }_{\text{n}}$ ，由引理3.2有$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}_1\right)$ 。

若$x_{u^{\prime }}<x_{v^{\prime }}$ ，去掉圈$C_h$ 上的边$u^{\prime }{u}^{″}$ ，并新加一条边$u^{″}{v}^{\prime }$ ，所得到的图记作$G_2$ ，则$G_2\in {\Phi }_{\text{n}}$ ，由引理3.2有$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}_2\right)$ 。

引理4.2 令图$G\in {\Phi }_{\text{n}}\backslash \left({\Phi }_{\text{n}}\cap S\right)$ 。对任意正整数$n\ge 7$ ，一定存在图$G\text{'}\text{'}\in S$ ，使得

$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}^{″}\right).$

证明 令$G$ 中具有公共端点u和v的三条内部点不相交的路分别为$P_{h+1}=u{u}_1\cdots u_{h-1}v$ 、$P_{k+1}=u{u^{\prime }}_1\cdots {u^{\prime }}_{k-1}v$ 和$P_{l+1}=u{u^{″}}_1\cdots {u^{″}}_{l-1}v$ 。不失一般性，假设$h\ge k\ge l\ge 1$ ，$k\ge 2$ 。

情形1 $l=1,h=k=2.$

1) 若$\left\{u,v,u_1,{u^{\prime }}_1\right\}$ 中恰有一点粘有悬挂树$T$ 。当$u\in V\left(T\right)$ 或$v\in V\left(T\right)$ 时，不妨设$u\in V\left(T\right)$ ，由于图$G\in {\Phi }_{\text{n}}\backslash \left({\Phi }_{\text{n}}\cap S\right)$ ，则$T$ 不可能是星或者双星。通过对$T$ 的所有非悬挂割边重复进行图变换1，可以得到${\theta }_{2,1,2}u\left(p,q\right)\in S$ 。因此，有$\mu \left(\overline{G}\right)<\mu \overline{\left({\theta }_{2,1,2}u\left(p,q\right)\right)}$ 。当$u_1\in V\left(T\right)$ 或${u^{\prime }}_1\in V\left(T\right)$ 时，不妨设$u_1\in V\left(T\right)$ 。由于图$G\in {\Phi }_n\backslash \left({\Phi }_n\cap S\right)$ ，则$T$ 不可能是星。通过对$T$ 的所有非悬挂割边重复进行图变换1，可以得到图${\theta }_{2,1,2}{u}_1\left(n-4\right)\in S$ 。因此，有$\mu \left(\overline{G}\right)<\mu \overline{\left({\theta }_{2,1,2}{u}_1\left(n-4\right)\right)}$ 。

2) 若$\left\{u,v,u_1,{u^{\prime }}_1\right\}$ 中至少有两个点粘有悬挂树。如果图$G$ 存在悬挂树非星，则通过对这棵悬挂的所有非悬挂割边重复进行图变换1，从悬挂树中构造出星，得到的新图记作$G_1$ ，由引理3.1可得$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}_1\right)$ 。若$G_1\in S$ ，则结论成立。否则，若图$G_1$ 中的点u和v都粘有悬挂星，比较u、v所对应$\mu \left({\overline{G}}_1\right)$ 的Perron向量中分量的大小，重复进行图变化2操作，去掉分量较小的点所连接的悬挂边，并将这些悬挂边与分量较大的点相连，得到的新图记作$G_2$ ，则有$\mu \left({\overline{G}}_1\right)<\mu \left({\overline{G}}_2\right)$ 。若$G_2\in S$ ，则结论得证。否则，若图$G_2$ 中的点u和${u^{\prime }}_1$ 都粘有悬挂星，比较u、${u^{\prime }}_1$ 所对应$\mu \left({\overline{G}}_2\right)$ 的Perron向量中分量的大小，重复进行图变化2操作，得到图${\theta }_{2,1,2}u{u}_1\left(p,q\right)\in S$ 或图${\theta }_{2,1,2}{u}_1{u^{\prime }}_1\left(p,q\right)\notin S$ ，则有$\mu \left({\overline{G}}_2\right)<\mu \overline{\left({\theta }_{2,1,2}u{u}_1\left(p,q\right)\right)}$ 和$\mu \left({\overline{G}}_2\right)<\mu \overline{\left({\theta }_{2,1,2}{u}_1{u^{\prime }}_1\left(p,q\right)\right)}$ 。比较图${\theta }_{2,1,2}{u}_1{u^{\prime }}_1\left(p,q\right)$ 中的点$u_1$ 和${u^{\prime }}_1$ 对应于$\mu \overline{\left({\theta }_{2,1,2}{u}_1{u^{\prime }}_1\left(p,q\right)\right)}$ 的Perron向量中分量的大小，重复进行图变化2操作，同样去掉分量较小的点所连接的悬挂边，并将这些悬挂边与分量较大的点相连，得到图${\theta }_{2,1,2}{u}_1\left(n-4\right)\in S$ ，则有$\mu \overline{\left({\theta }_{2,1,2}{u}_1{u^{\prime }}_1\left(p,q\right)\right)}<\mu \overline{\left({\theta }_{2,1,2}{u}_1\left(n-4\right)\right)}$ 。综上，结论得证。若图$G_1$ 的点u和v两点中只有一点粘有悬挂星，不妨假设粘有悬挂星的是u和${\text{u'}}_1$ ，对顶点u和${u^{\prime }}_1$ 进行引理3.2的操作，得到图${\theta }_{2,1,2}{u}_1\left(n-4\right)\in S$ 或图${\theta }_{2,1,2}u{u}_1\left(p,q\right)\in S$ ，则有$\mu \left({\overline{G}}_1\right)<\mu (\overline{\left({\theta }_{2,1,2}{u}_1\left(n-4\right)\right)}$ 和$\mu \left({\overline{G}}_1\right)<\mu \overline{\left({\theta }_{2,1,2}u{u}_1\left(p,q\right)\right)}$ 。结论依然成立。最后考虑图$G_1$ 的点u和v都不粘有悬挂星的情况，此时$G_1\cong {\theta }_{2,1,2}{u}_1{u^{\prime }}_1\left(p,q\right)$ ，由上述分析可知结论成立。综上，可以从图$G$ 中重复应用引理3.2，最终得到图${\theta }_{2,1,2}{u}_1\left(n-4\right)\in S$ 或图${\theta }_{2,1,2}{\text{uu}}_1(\text{p,q)}\in S$ 。

情形2 $h=k=l=2.$

1) 若$\left\{u,u_1,{u^{\prime }}_1,{u^{″}}_1,v\right\}$ 中恰有一点粘有悬挂树$T$ 。由于图$G\in {\Phi }_{\text{n}}\backslash \left({\Phi }_{\text{n}}\cap S\right)$ ，则$T$ 非星。通过对$T$ 的所有非悬挂割边重复应用引理3.1的操作，可以得到图${\theta }_{2,2,2}u\left(n-5\right)\in S$ 或图${\theta }_{2,2,2}{u}_1\left(n-5\right)\in S$ 。则有$\mu \left(\overline{G}\right)<\mu \overline{\left({\theta }_{2,2,2}u\left(n-5\right)\right)}$ 和$\mu \left(\overline{G}\right)<\mu \overline{\left({\theta }_{2,2,2}{u}_1\left(n-5\right)\right)}$ 。结论成立。

2) 若$\left\{u,u_1,{u^{\prime }}_1,{u^{″}}_1,v\right\}$ 中至少有两个点粘有悬挂树。如果图$G$ 存在悬挂树非星，则通过对这棵悬挂的所有非悬挂割边重复进行图变换1，从悬挂树中构造出一颗星，得到的新图记作${G^{\prime }}_1$ ，由引理3.1可得$\mu \left(\overline{G}\right)<\mu \left({{\overline{G}}^{\prime }}_1\right)$ 。若${G^{\prime }}_1\in S$ ，则结论成立。否则，若图${G^{\prime }}_1$ 中的点u和v都粘有悬挂星，比较u、v所对应$\mu \left({{\overline{G}}^{\prime }}_1\right)$ 的Perron向量中分量的大小，重复进行图变化2操作，去掉分量较小的点所连接的悬挂边，并将这些悬挂边与分量较大的点相连，得到的新图记作${G^{\prime }}_2$ ，则有$\mu \left({{\overline{G}}^{\prime }}_1\right)<\mu \left({{\overline{G}}^{\prime }}_2\right)$ 。若$G{\text{'}}_2\in S$ ，则结论得证。否则，若图${G^{\prime }}_2$ 中的点u和${u^{\prime }}_1$ 都粘有悬挂星，比较u、${u^{\prime }}_1$ 所对应$\mu \left({{\overline{G}}^{\prime }}_2\right)$ 的Perron向量中分量的大小，重复进行图变化2操作，得到图${\theta }_{2,2,2}u{u}_1\left(p,q\right)\in S$ 或图${\theta }_{2,2,2}{u}_1{u^{\prime }}_1\left(p,q\right)\notin S$ ，则有$\mu \left({{\overline{G}}^{\prime }}_2\right)<\mu \overline{\left({\theta }_{2,2,2}u{u}_1\left(p,q\right)\right)}$ 和$\mu \left({{\overline{G}}^{\prime }}_2\right)<\mu \overline{\left({\theta }_{2,2,2}{u}_1{u^{\prime }}_1\left(p,q\right)\right)}$ 。比较图${\theta }_{2,2,2}{u}_1{u^{\prime }}_1\left(p,q\right)$ 中的点$u_1$ 和${u^{\prime }}_1$ 对应于$\mu \overline{\left({\theta }_{2,2,2}{u}_1{u^{\prime }}_1\left(p,q\right)\right)}$ 的Perron向量中分量的大小，重复进行图变化2操作，同样去掉分量较小的点所连接的悬挂边，并将这些悬挂边与分量较大的点相连，得到图${\theta }_{2,2,2}{u}_1\left(n-4\right)\in S$ ，则有$\mu \overline{\left({\theta }_{2,2,2}{u}_1{u^{\prime }}_1\left(p,q\right)\right)}<\mu \overline{\left({\theta }_{2,2,2}{u}_1\left(n-4\right)\right)}$ 。综上，结论得证。若图${G^{\prime }}_1$ 的点u和v两点中只有一点粘有悬挂星，不妨假设粘有悬挂星的是$u$ 和${u^{\prime }}_1$ ，对顶点$u$ 和${u^{\prime }}_1$ 进行引理3.2的操作，得到图${\theta }_{2,2,2}{u}_1\left(n-5\right)\in S$ 或图${\theta }_{2,2,2}u{u}_1\left(p,q\right)\in S$ ，则有$\mu \left({{\overline{G}}^{\prime }}_1\right)<\mu \overline{\left({\theta }_{2,2,2}{u}_1\left(n-5\right)\right)}$ 和$\mu \left({{\overline{G}}^{\prime }}_1\right)<\mu \overline{\left({\theta }_{2,2,2}u{u}_1\left(p,q\right)\right)}$ 。结论依然成立。最后考虑图${G^{\prime }}_1$ 的点u和v都不粘有悬挂星的情况，此时${G^{\prime }}_1\cong {\theta }_{2,2,2}{u}_1{u^{\prime }}_1\left(p,q\right)$ ，由上述分析可知结论成立。综上，可以从图$G$ 中重复应用引理3.2，最终得到图${\theta }_{2,2,2}u\left(n-4\right)\in S$ 或图${\theta }_{2,2,2}{u}_1\left(n-4\right)\in S$ 或图${\theta }_{2,2,2}u{u}_1\left(p,q\right)\in S$ 。

情形3 $h=3,k=2,l=1.$

1) 若$\left\{u,v,u_1,u_2,{u^{\prime }}_1\right\}$ 中恰有一点粘有悬挂树$T$ 。当$T$ 是星时，由于图$G\in {\Phi }_{\text{n}}\backslash \left({\Phi }_{\text{n}}\cap S\right)$ ，则$G\cong {\theta }_{3,1,2}{u^{\prime }}_1\left(n-5\right)$ 。通过对图${\theta }_{3,1,2}{u^{\prime }}_1\left(n-5\right)$ 中圈上的任意两点重复进行引理3.2的操作，比较这两点对应于$\mu \overline{\left({\theta }_{3,1,2}{u^{\prime }}_1\left(n-5\right)\right)}$ 的Perron向量中分量的大小，去掉分量较小的点所连接的悬挂边，并将这些悬挂边与分量较大的点相连，可以得到图${\theta }_{3,1,2}u\left(n-5\right)\in S$ 或图${\theta }_{3,1,2}u{u}_1\left(p,q\right)\in S$ 或图${\theta }_{3,0,3}{u}_1\left(n-5\right)\in S$ 或图${\theta }_{2,1,2}{u}_1{u^{\prime }}_1\left(n-5,1\right)\notin S$ ，由引理3.2则有$\mu \left(\overline{G}\right)<\mu \overline{\left({\theta }_{3,1,2}u\left(n-5\right)\right)}$ ，$\mu \left(\overline{G}\right)<\mu \overline{\left({\theta }_{3,1,2}u{u}_1\left(p,q\right)\right)}$ 和$\mu \left(\overline{G}\right)<\mu \overline{\left({\theta }_{3,0,3}{u}_1\left(n-5\right)\right)}$ ，又由情形1可知$\mu \overline{\left({\theta }_{2,1,2}{u}_1{u^{\prime }}_1\left(n-5,1\right)\right)}<\mu \overline{\left({\theta }_{2,1,2}{u}_1\left(n-4\right)\right)}$ ，结论成立。若$T$ 是非星，通过对悬挂树$T$ 的所有非悬挂割边重复进行图变换1，最终得到图${\theta }_{3,1,2}u\left(n-5\right)\in S$ 或图${\theta }_{3,1,2}{u}_1\left(n-5\right)\in S$ 或图${\theta }_{3,1,2}{u^{\prime }}_1\left(n-5\right)\notin S$ ，由引理3.1可知结论成立。

2) 若$\left\{u,v,u_1,u_2,{u^{\prime }}_1\right\}$ 中至少有两个点粘有悬挂树。与情形1中2)相似，利用引理3.1和3.2，最终得到图${\theta }_{3,1,2}u\left(n-5\right)\in S$ 或图${\theta }_{3,1,2}{u}_1\left(n-5\right)\in S$ 或图${\theta }_{3,1,2}u{u}_1\left(p,q\right)\in S$ 或图${\theta }_{3,1,2}uv\left(p,q\right)\in S$ 或图${\theta }_{3,1,2}{u^{\prime }}_1\left(n-5\right)\notin S$ (1)中的情况)，因此结论得证。

情形4 $h=k=3,l=1.$

1) 若$\left\{u,v,u_1,u_2,{u^{\prime }}_1,{u^{\prime }}_2\right\}$ 中恰有一点粘有悬挂树$T$ 。当$T$ 是星时，由于图$G\in {\Phi }_{\text{n}}\backslash \left({\Phi }_{\text{n}}\cap S\right)$ ，则$G\cong {\theta }_{3,1,3}{u}_1\left(n-6\right)$ 。通过对图${\theta }_{3,1,3}{u}_1\left(n-6\right)$ 中圈上的任意两点重复进行引理3.2的操作，比较这两点对应于$\mu \overline{\left({\theta }_{3,1,3}{u}_1\left(n-6\right)\right)}$ 的Perron向量中分量的大小，去掉分量较小的点所连接的悬挂边，并将这些悬挂边与分量较大的点相连，可以得到图$R_{3,0,3}u{u}_1\left(p,q\right)\in S$ 或图${\theta }_{3,1,2}u\left(n-5\right)\in S$ 或图${\theta }_{3,1,3}u\left(n-6\right)\in S$ 或图$R_{2,2,2}u{u}_1\left(p,q\right)\in S$ 或图${\theta }_{3,1,2}{u}_1\left(n-5\right)\in S$ 或图${\theta }_{3,1,2}u{u}_1\left(p,q\right)\in S$ 或图${\theta }_{3,1,2}{u^{\prime }}_1\left(n-5\right)\notin S$ (情形3的情况)或图${\theta }_{3,1,2}u{u}_2\left(p,q\right)\notin S$ (情形3的情况)或图${\theta }_{2,2,2}{u}_1{u^{\prime }}_1\left(p,q\right)\notin S$ (情形2的情况)或图${\theta }_{3,1,2}u{u^{\prime }}_1\left(p,q\right)\notin S$ (情形3的情况)或图${\theta }_{3,1,2}{u}_1{u^{\prime }}_1\left(p,q\right)\notin S$ (情形3的情况)，结合情形2和情形3可知结论成立。若$T$ 是非星，通过对悬挂树$T$ 的所有非悬挂割边重复进行图变换1，最终得到图${\theta }_{3,1,2}u\left(n-6\right)\in S$ 或图${\theta }_{3,1,3}{u}_1\left(n-6\right)\notin S$ ，由引理3.1可知结论成立。

2) 若$\left\{u,v,u_1,u_2,{u^{\prime }}_1,{u^{\prime }}_2\right\}$ 中至少有两个点粘有悬挂树。与情形1中2)相似，利用引理3.1和3.2，最终得到图${\theta }_{3,1,3}u\left(n-6\right)\in S$ 或图${\theta }_{3,1,3}uv\left(p,q\right)\in S$ 或图${\theta }_{3,1,3}{u}_1\left(n-6\right)\notin S$ (1)中的情况)，因此结论得证。

情形5 $h\ge 4,k\ge 2,l=1.$

通过对图$G$ 中圈上的任意两点重复应用引理3.2的操作，比较这两点对应于$\mu \left(\overline{G}\right)$ 的Perron向量中分量的大小，去掉分量较小的点所连接的悬挂边，并将这些悬挂边与分量较大的点相连，反复进行上述操作，最终得到图$G_3\in {\Phi }_{2,1,2}$ (情形1的情况)或图$G_4\in {\Phi }_{2,2,2}$ (情形2的情况)或图$G_5\in {\Phi }_{3,1,2}$ (情形3的情况)或图$G_6\in {\Phi }_{3,1,3}$ (情形4的情况)，因此结论得证。

情形6 $h\ge 3,k\ge 2,l-2.$

反复对图$G$ 中进行类似情形5的操作，最终得到图$G_7\in {\Phi }_{2,1,2}$ (情形1的情况)或图$G_8\in {\Phi }_{2,2,2}$ (情形2的情况)或图$G_9\in {\Phi }_{3,1,2}$ (情形3的情况)或图$G_{10}\in {\Phi }_{3,1,3}$ (情形4的情况)，因此结论得证。

情形7 $h\ge k\ge l.$

反复对图$G$ 中进行类似情形5的操作，最终得到图$G_{11}\in {\Phi }_{2,1,2}$ (情形1的情况)或图$G_{12}\in {\Phi }_{2,2,2}$ (情形2的情况)或图$G_{13}\in {\Phi }_{3,1,2}$ (情形3的情况)或图$G_{14}\in {\Phi }_{3,1,3}$ (情形4的情况)，因此结论得证。

综上所述，一定存在图$G^{″}\in S$ ，使得$\mu \left(\overline{G}\right)<\mu \left({\overline{G}}^{″}\right)$ 。

结合引理4.1与引理4.2，则有下述定理成立。

定理4.3 设图$G\in B_n$ 且$\overline{G}$ 连通。对于任意正整数$n\ge 7$ ，若$\tilde{G}\in S$ ，则有

$\mu \left(\overline{G}\right)<\mu \left(\tilde{G}\right)\text{.}$

5. 小结

本文研究双圈图补图的距离无符号拉普拉斯谱半径。首先将所有双圈图进行分类，并且介绍两种增加补图距离无符号拉普拉斯谱半径的图变换，最终在n阶双圈图补图中确定了距离无符号拉普拉斯谱半径最大时所落在的图类集合。对补图的距离无符号拉普拉斯谱半径的研究，还存在着可以去尝试研究的地方，除了研究双圈图，还可以研究其他图类，比如三圈图、多圈图、二部图、完全多部图等；此外，还可以固定某一参数进行研究，如固定直径、悬挂点数、匹配数、最大度最小度等。