卢鹏丽，王旭柱，陈作汉

(兰州理工大学计算机与通信学院，甘肃兰州730050)

本文所涉及的图都是简单无向图.设图G= (V(G)，E(G))的顶点集和边集分别为V(G)={v1，v2，…，vn}和E(G)，其中v1，v2，…，vn按顶点的度非递增排列.设A(G)=(auv)是图G的邻接矩阵，当u和v相邻时，auv=1，当u和v不相邻时，auv=0.di= di(G)=dG(vi)是顶点vi的度，D(G)是对角元素为{d1，d2，…，dn}的n×n对角矩阵，则矩阵L(G)= D(G)－A(G)称为图G的Laplacian矩阵.显然，L(G)是一个最小特征值为0的半正定对称矩阵.设μ1≥μ2≥…≥μn(=0)是L(G)的特征值，它们构成了图G的Laplacian谱.如果2个图有相同的Laplacian谱，就说他们是Laplacian同谱图.如果与图G同Laplacian谱的图都与图G同构，则称图G可由它的Laplacian谱确定.

关于“哪些图可由它们的谱确定?”这个问题的背景，建议读者参阅文献［1－2］，到目前为止，只有少量结构特殊的图被证明了能由它们的谱确定［1－4］.因此，寻找新的谱确定图是一个有趣的问题.

文献［3］证明了lollipop图(表示为Cn，g，它是在一条顶点数为n－g的路图的一个悬挂点上连接一个圈Cg得到的图)能由其Laplacian谱确定.文献［5］证明了图H(n;q，n1，n2)(它是在一个圈Cq的同一个顶点上悬挂2条路Pn1，Pn2而构成的图，n是它的顶点数)能由其Laplacian谱确定.

本文证明了图H(n;q，n1，n2，n3)可由其Laplacian谱确定.

1 基本引理

引理1［1］对于图G，由其邻接谱和Laplacian谱可得图G的下列性质:

1)顶点数，

2)边数，

3)G是否是正则图.

由其邻接谱可得:

4)任意长度的闭回路数，

5)图G是否是二部图.

由其Laplacian谱可得:

6)分支数目，

7)生成树数目，

8)顶点的度平方和.

引理2［1］设N是一个n×n的对称矩阵，其特征根为α1≥α2≥…≥αn.N的m阶主子矩阵的特征根为α1'≥α2'≥…≥αm'，则αi≥αi'≥αn－m+i，i= 1，2，…，m.

引理3［6］设A=［aij］是一个n阶方阵，令

是矩阵A第i行元素的绝对值的和，则

式中:ρ(A)是矩阵A的最大特征值.相似地，对于矩阵……