张晓艳，张海霞

（太原科技大学 应用科学学院，山西 太原 030024）

设G=(V(G),E(G))是n阶简单图，其中V(G) = {v1,v2, …,vn}为顶点集，E(G) ={e1,e2, …,em}为边集。对于任意v∈V(G)，用Nk(v)表示在G中距离顶点v为k的所有顶点的集合，特别地，N(v) =N1(v)和dv=|N(v)|分别是v的邻集和度。对于S,T⊆V(G)且S∩T= ∅，设e(S,T)为S与T之间的边数，G[S]是由S诱导的G的子图，eG[S]表示由S诱导的G的子图的边数。通常我们用Kn表示n阶完全图，kG表示G的k个复制图的不相交并集。G∇H是通过不相交并集G∪H增加G与H之间的所有边得到的图，特别地，Fk=K1∇kK2，Sn,k=Kk∇(n-k)K1。

令图G的邻接矩阵为A(G)，G的度对角矩阵为D(G)= diag{dG(vi),vi∈V(G)}，两矩阵之和称为图G的无符号拉普拉斯矩阵，即Q(G)=D(G)+A(G)。2017年，Nikiforov[1]提出了将图的邻接矩阵和无符号拉普拉斯矩阵合并进行研究的想法，定义了一个新的Aα(G)矩阵，该矩阵是D(G)和A(G)的线性组合，即Aα(G)=αD(G)+(1 -α)A(G),α∈[0, 1]，显然有。

由于Aα(G)是实对称矩阵，因此其特征值均为实数。Aα(G)的最大特征值叫做图G的Aα谱半径，用λ1(G)来表示。给定一个图G，如果它不包含H作为子图，我们说G是无H的。记ex(n,H)表示H的Turán数，它是n阶无H图的最大边数。设Ex(n,H)为n阶无H图具有ex(n,H)条边的图的集合。确定ex(n,H)和Ex(n,H)中的图的特征是极值图理论中的一个基本问题(称为Turán-type 问题)[2-3]。1995 年，Erdos 等[4]考虑了不包含Fk图的Turán-type问题，并给出了以下结果：

定理1[4]对于k≥1且n≥50k2，则有

在边的数量尽可能地大的情况下，其极值图的构造如下：

当k(n≥4k- 1)是奇数，那么唯一极值图的构造是通过取一个完全等二部图，并在一侧嵌入两个顶点集不相交的图Kk。如果k(n≥4k- 3)是偶数，那么每个极值图的构造方法是取一个完全等二部图，在一侧嵌入一个有2k- 1个顶点、条边、最大度为k- 1的图。

最近，Cioabă 等[5]研究了不含Fk的图的Brualdi-Solheid-Turán 型问题，Zhao 等[6]研究了不含Fk的图的最大无符号拉普拉斯谱半径，给出了如下结果：

定理2[5]设G是一个不包含Fk的n阶图，对于足够大的n，如果G具有最大的谱半径，则有G∈Ex(n,Fk)，其中Ex(n,Fk)由定理1中给出的极值图组成。

本文受文献[5-6]的启发，重点研究了不包含Fk的n阶图的最大Aα谱半径，并证明如下定理：

定理3 设k≥2 且n≥3k2-k- 2，如果G是一个不包含Fk的n阶图，那么对于，有λ1(G)≤λ1(Sn,k)，等式成立当且仅当G≅Sn,k。

1 定理3的证明

首先，关于矩阵等价划分的一些定义如下：

设M是n阶实对称矩阵，且设N={1, 2,…,n}，给出一个划分∏:N=N1∪N2∪…∪Nt，矩阵M可以相应地划分为

其中对于1 ≤i,j≤t，Mij是一个ni×nj的矩阵，bij表示Mij的平均行和，即bij是Mij所有项的和除以行数所得到的结果，那么B(M) =(bij)被称为M的商矩阵。如果对于每对i,j，Mij具有恒定的行和，那么B被称为M的等价商矩阵，划分称为等价划分。

下面的一些引理对于定理3的证明是至关重要的。

引理1[7-8]设M是实对称矩阵，B∏是M的等价商矩阵，那么B∏的特征值也是M的特征值。此外，如果M是非负不可约矩阵，则有λ1(M) =λ1(B∏)。

引理2[9]如果M1和M2是两个非负对称矩阵，使得M1-M2也是非负的，则有λ1(M1)≥λ1(M2)。

当图G是一个不包含kK2的图，则有α′≤k- 1。根据引理4，把α′=k- 1代入，可得下面的推论：

在接下来的这一部分来证明定理3。

证明假设G是所有不包含Fk的n阶图中具有最大Aα谱半径的图，其中，且G是连通图，通过λ1(G)的最大性得到下面两个事实：

事实1对于∀v∈V(G)，G[N(v)]不包含kK2，显然这是成立的。

事实2对于∀v∈V(G)，有V(G)={v}∪N(v) ∪N2(v) (|N2(v)|=n- 1 -dv)。

证明由于G是所有不包含Fk的n阶图中具有最大Aα谱半径的图，所以G不是完全图，且对于任意uv∉E(G)，G+uv是包含Fk的图，因此，G的任意两个不相邻的顶点至少有一个共同的邻点，则有上述结论成立。

注意到Sn,k=Kk∇(n-k)K1是不包含Fk的。通过引理5的式（1）可得

再根据引理3得到

结合上面两个式子有

证明分以下几种情形进行讨论：

情形1du≤2k- 2

情形2du= 2k- 1

声明2G[N(u)]是Sdu,k-1的一个生成子图。

证明首先G[N(u)]中包含一个k- 1匹配P，否则通过引理4可得

这与声明1的区间矛盾。

设 匹 配P={risi:1 ≤i≤k- 1}，R={r1,r2, …,rk-1}，S={s1,s2, …,sk-1}，T=N(u)(R∪S)。因 为G[N(u)]是一个不包含kK2的图，由事实1知T一定是一个独立集。同理，我们断言，对于每一个1 ≤i≤k- 1，N(ri) ∩T和N(si) ∩T中至少有一个是空集，或者对于某一个ti∈T，N(si) ∩T=N(ri) ∩T={ti}，且设p表示1≤i≤k- 1的个数，使得N(ri) ∩T= ∅或N(si) ∩T= ∅，如果p≤k- 2，则有

因此得到

与声明1的区间构成矛盾，因此必须有p=k- 1。

对于每个1 ≤i≤k- 1有N(ri)∩T= ∅或者N(si)∩T= ∅，不失一般性，我们假设对于所有1 ≤i≤k- 1有N(si) ∩T= ∅，即S与T之间无边。

下面来证明S也是一个独立集。事实上，如果G[S]中存在某条边sisj(i≠j)，如上所示，则N(ri) ∩T和N(rj) ∩T中 至 少 有 一 个 是 空 集，或 者 对 于 某 个t∈T，N(ri) ∩T=N(rj) ∩T={t}，有e({ri,rj},T) ≤max{2,du- 2(k- 1)}=du- 2(k- 1),因此可得

通过计算，与声明1 的式（3）产生矛盾，由此得到S∪T是一个独立集合。注意到|R|=|S|=k- 1 且|T|=du-2(k- 1)，那么G[N(u)]是Sdu,k-1的一个生成子图。

设R={r1,r2, …,rk-1},S={s1,s2, …,sk-1}，且T是在声明2 中所定义，则有N(u)=R∪S∪T。设Y=S∪T,X={u}∪R∪N2(u)，注意到Y是一个独立集合，那么Y最多有k(k- 1) - 1个顶点与X{u}的所有顶点不相邻，否则，从声明2中可以得出

通过计算，与声明1的式（3）区间产生矛盾。

注意到图G是不包含Fk的图，那么可以得出，X的每个顶点在G[X]中的度最大为k- 1。设G*=G[X]∇G[Y]=G[X]∇(du-k+ 1)K1，那么G就是G*的生成子图。取

结合上面的两个公式可以推出du≥n- 1，故而du=n- 1。根据声明2可得G是K1∇Sn-1,k-1的生成子图，因此当G≅Sn,k时λ1(G)最大。

2 结论

本文研究了无相交三角形Aα谱半径的问题，当α∈(]，k≥2且n≥3k2-k- 2时，对其极值图进行了刻画，并且得到了当G≅Sn,k时具有的最大Aα谱半径。