给定最小度和边连通度的图的最大无符号拉普拉斯谱半径

方 怡，余桂东

（1.铜陵职业技术学院，安徽铜陵244061；2.合肥幼儿师范高等专科学校，安徽合肥230013；3.安庆师范大学数理学院，安徽安庆246133）

本文所讨论的图均为有限简单无向图，设G=(V(G),E(G))是一个n阶简单连通图，其顶点集V(G)={v1,v2,v3,…,vn}，顶点v∈V(G)的邻域定义为NG(v)={u：uv∈E(G)}，顶点v的度dG(v)=|NG(v)|且N[v]=N(u)∪{v}。G的最小度记为δ(G)，如果A、B是V(G)中互不相交的子集，则[A,B]={uv∈E(G)|u∈A,v∈B}。

S是V(G)的一个子集，设N(S)=∪v∈SN(v)且G[S]是由S产生的G的导出子图。如果图G中任意两点均有一条路连接，则称图G是连通的。假设U⊆E(G)，如果G-U是不连通的，则称U是G的一个边割。G的边连通度定义为k′(G)或k′，是G的边割的最小基数。很明显，k′≤δ。

图G的度对角矩阵为D(G)=diag(dG(v1),dG(v2),dG(v3),…,dG(vn))。图G的邻接矩阵定义为A(G)=(aij)n×n，其中当vi、vj相邻时，aij=1，否则aij=0。图G的无符号拉普拉斯矩阵定义为Q(G)=D(G)+A(G)。由于A(G)为实对称矩阵，故其特征值均为实数，可进行排序，我们称A(G)的最大特征值为图G的谱半径，记为μ(G)；称Q(G)的最大特征值为图G的无符号拉普拉斯谱半径，记为q(G)。与μ(G)对应的全正向量称为G的Perron向量。

近年来，关于图的谱半径和无符号拉普拉斯谱半径的研究取得了许多有意义的成果，特别是在给定的一类图中寻找最大的谱半径和无符号拉普拉斯谱半径[1-4]。文献[4]报道了在有n个顶点、最小度为δ且边连通度k′＜δ这一类图中找谱半径最大的图的方法，受此启发，本文主要研究有n个顶点、最小度为δ且边连通度k′＜δ这一类图中无符号拉普拉斯谱半径最大的图。设是一个阶为n、最小度为δ且边连通度为k′的}图，其中n≥2,δ≥k′≥0。

在给出主要结论之前，先介绍一些引理和特殊符号。

对于一个图G，不必是连通的。对于图G的点集V(G)定义这两个符号≥G和～G：

u≥Gv当且仅当N(u){v}⊇N(v){u}，u～Gv当且仅当N(u){v}=N(v){u}。

如果N(u){v}⊃N(v){u}，则记作u＞Gv，⊃表示严格包含。

引理1[5]设G是最小度为δ的图，U是V(G)的非空真子集，如果|[U,VU]|≤δ-1，则|U|≥δ+1。

引理2[6]设G是连通图，G′是G的一个真子图，则q(G)′＜q(G)。

引理3[7]设u、v是连通图G中两个不同的点，x是Q(G)的Perron向量。

（1）如果u＞Gv，则xu＞xv；

（2）如果u～Gv，则xu=xv。

引理4[8]设G是连通图，其中u、v是G的两个点。假设v1,v2,v3,…,vs∈N(v)N(u)(1≤s≤dG(v))且x=(x1,x2,x3,…,xn)T是Q(G)的Perron向量，其中xi与点vi(1≤i≤n)相对应。设G*是通过在G中删除vvi边添加uvi边获得的，1≤i≤s。如果xu≥xv，则q(G)＜q(G*)。

引理5[9]设G=(V,E)是一个n阶图，则，当且仅当x是q(G)对应的特征向量时，等式成立。

定理1如果在这一类图中G0的无符号拉普拉斯谱半径最大，其中1≤k′＜δ，则，其中是从Kδ+1和Kn-δ-1之间加入k′条边获得的图。

证明设G0是中的图，满足是q(G0)的Perron向量。设U=[A,B]是一个边割，满足|U|=k′。根据引理1，δ+1≤|A|≤n-δ-1，δ+1≤|B|≤nδ-1。设v0是度为δ的点，不失一般性，假设v0∈A，NG0[A](v0)={v1,v2,v3,…,vs}和NG0[B](v0)={vs+1,vs+2,vs+3,…,vδ}。由引理2可知G0[A]-v0和G0[B]都是团。

由引理2和1≤k′＜δ的条件知，要证明，只 须 证 明min{|A|,|B|}=δ+1。假 设min{|A|,|B|}≥δ+2，则有下面2个断言。

断言1对A{v0}（或B）中任一对点u和v，则xu≥xv当且仅当N(u){v}⊃N(v){u}。

证明根据引理3中的条件（1）可知，充分性是成立的。

下面证明必要性：假设u和v是A{v0}中的点且满足xu≥xv，但是，则存在点p∈N(v){u}，但p∉N(u){v}。假设p∈B，令H=G0-pv+pu。由于min{|A|,|B|}≥δ+2，G0[A]-v0和G0[B]都是团，我们得到δ(H)=δ且U{pv}∪{pu}是H的一个满足最小基数的边割。因此，H。结合引理4可得，q(H)＞q(G0)，这与G0的选择矛盾。

因此，假设p∈A且。因为G0[A]-v0是一个团，得到p=v0。现在设H′=G0-v0v+v0u，则H。结合引理4可得，q(H)＞q(G0)，这与G0的选择矛盾。因此，对于A{v0}中的一对点u和v，xu≥xv总是表示。根据引理3中条件（2）可知，当N(u){v}=N(v){u}时xu=xv。于是若xu＞xv，则有N(u){v}⊃N(v){u}。通过相似的讨论，也可以证明在B中的一对点u和v也是满足上述情况的。

断言2[AN[v0],B]=∅。

证明假设[AN[v0],B]≠∅。设u∈AN[v0]和v∈B是两个点，且满足uv∈[AN[v0],B]。注意对于1≤i≤s，v0∈N(vi)且v0∉N(u)，又根据断言1，N(vi){u}⊃N(u){vi}，1≤i≤s。由于v∈N(u){vi}，得到v∈N(vi)，其中1≤i≤s，进而可得|[A,B]|≥(δ-s)+s+1=δ+1，这与|[A,B]|=k′＜δ矛盾。

现在定义集合A′是由AN[v0]中任意取|A|-δ-1个点组成，集合B′是由BN(A)中任意取|B|-δ-1个点组成。根据断言2和B′的选择知道[A′,B]=[A,B′]=∅。由于min{|A|,|B|}≥δ+2且|[A,B]|=k′＜δ，有|A′|≥1,|B′|≥1。现考虑以下两种情况：

情况1

在这种情况下，设H是从G0中去掉[A′,A-A′]中所有边且增加G0[A-A′]和G0[A′∪B]中所有可能的边得到的，这样H[A-A′]和H[A′∪B]都是团，则，结合引理5可得

这与G0的选择矛盾。

情况2

这与G0的选择矛盾。