图H(p，pK16）的拉普拉斯谱刻画

赵绍玉

（三明学院 信息工程学院，福建 三明 365004）

这里考虑的都是有限、无向、连通的简单图，取V（G),E（G),ni（G)分别表示图G的顶点集、边集和度为 i顶点数。图 G 的邻接矩阵 A（G)=（aij）n×n,，其中 aij是 1当且仅当 vi和 vj相邻，否则是 0。用 di表示图 G 中的顶点 vi的度数。D（G）=diag（d1，d2，…，dn)是由顶点的度构成的对角矩阵。矩阵 L（G）=D（G）-A（G）称为图 G 的 Laplacian 矩阵。多项式 P(A（G);λ)=det（λIn-A（G)）=λn+a1λn-1+…+an,称为图G 的邻接特征多项式,P(L（G);μ)=det（μIn-L（G)）=μn+b1μn-1+…+bn称为图 G 的 Laplacian 特征多项式，In是单位矩阵。设 λi（i=1，……，n）是 A（G)的特征值,它们的集合构成了图 G 的邻接谱;μi（i=1，……，n）是L（G)的特征值，它们构成的集合称为图G的Laplacian谱。若两个图的邻接谱(Laplacian谱)相同，就说它们是邻接(Laplacian)同谱图。同样,若两个图的Laplacian谱相同，则说它们是Laplacian同谱图。与图G邻接同谱的图都与G同构，称图G可由其邻接谱确定。与图Laplacian同谱的图都与同构，称图可由其Laplacian谱确定。图谱的确定问题，最早由Günthard和Primas提出[1],起初主要用于化学方面的研究;直到2003年,这一问题再次被Van Dam和Haemers提出[2],才引起了广泛的关注,得到了很多研究成果[3-11]。用H（p，tK1，m）表示具有tm+p个顶点的单圈图,它是由圈Cp连续相邻的t（1≤t≤p）个顶点分别与星 K1，m的中心重合而得到的。当 t=1 时，卢鹏丽[4]证明了章鱼图 H（p，tK1，m）是由它的拉普拉斯谱确定的;Bu C J等[5]证明了H（p，pK1，2）是拉普拉斯谱确定的;王陆华[6]证明了图H（p，（p-1）K1，2）是拉普拉斯谱确定的，特别当 p 为偶数时，图 H（p，2K1，2），H（p，3K1，2），H（p，（p-3）K1，2），H（p，（p-2）K1，2）也都是由其拉普拉斯谱确定。梅若星等[7]证明了单圈图 H（p，pK1，3），H（p，pK1，4）和 H（p，（p-1）K1，3）分别是由其拉普拉斯谱确定的。并且当 p 为偶数时，H（p，2K1，3），H（p，（p-3）K1，3）和H（p，（p-2）K1，3）也分别由其拉普拉斯谱确定。孙秋实等[8]证明了单圈图 H（p，pK1，5）和 H（p，（p-1）K1，4）是由其拉普拉斯谱确定的，而且当 p 为偶数时，H（p，2K1，4），H（p，（p-3）K1，4）和 H（p，（p-2）K1，4）也分别由其拉普拉斯谱确定。

前述这些论文，只是研究了单圈图 H（p，pK1，m）（1≤m≤5）的拉普拉斯谱确定情况，而对于更复杂、更一般单圈图H（p，pK1，m）（6≤m）的拉普拉斯谱确定问题未见报道，所以，本文继续研究了单圈图 H（p，pK1，m）（m≥6）的拉普拉斯谱确定问题，证明了单圈图 H（p，pK1，6）是由其拉普拉斯谱确定的。

1 基本引理

引理1[3]若图G和图H是拉普拉斯同谱图,则

(1)图G和图H具有相同的顶点数和边数；

(2)图G和图H顶点度的平方和相等。

引理2[9]设图G是一个含有圈Ck的连通单圈图。若图G和图G'是拉普拉斯同谱的，则图G'也是一个与图G具有相同顶点数和边数、含有圈Ck的连通单圈图，并且

引理3[10]非空集合E（G）、V（G）分别表示图G的顶点集和边集，则有

其中Δ是图G的最大的顶点度，mi表示图G中与顶点vi邻接的顶点的度数的平均值。

引理4[11]设ni图G有n个顶点，是它的补图，则

2 主要结果

本节证明了单圈图是由其拉普拉斯谱确定的，并推出它的补图也是由其拉普拉斯谱确定的。

定理 1图 H（p，pK1，6）是由其拉普拉斯谱确定的。

证明令G=H（p，pK1，6）,假设图G'和图G具有相同的拉普拉斯谱，则由引理1可知,图G'是一个具有7p个顶点7p条边且含有圈Cp的连通单圈图。由引理3得

所以Δ≤9。设是图G中度为i的顶点个数。由引理1和引理2知

由此推出

因为 n8，n9≥0为整数且 p为大于等于 3的任意整数，令 p=3，由（10）可得 n9=0，n8≤p，将 n9=0代入（9）可得

由（2）和（11）得 70p≤20n7+70n8≤4n5+15n6+36n7+70n8≤70p

由此可得 4n5+15n6+16n7≤0，又因为 n5，n6，n7为大于等于 0的整数，所以 n5=n6=n7=0，将 n7=0代入（11）可得 n8≥p，所以 n8=p。进而可解得 n2=n3=n4=0，n1=6p。所以图 G'的序列 d（G'）=（8p，16p）。因为具有刻度序列（8p，16p）且 含有 Cp的连通单圈图只能是形如图 H（p，pK1，6）的图，所以 G'≌G。因此单圈图 H（p，pK1，6）是由其拉斯拉普谱确定的。

推论1图H（p，pK1，6）的补图可由其拉普拉斯谱确定的。

证明由引理4可知，图H（p，pK1，6）的补图也可由其拉普拉斯谱确定。

3 结论

本文利用Laplacian同谱图的一些性质，通过对同谱图顶点的度数进行讨论，证明了单圈图H（p，pK1，6）是由其 Laplacian 谱确定的，进一步补充了对单圈图 H（p，pK1，m）的研究，具有一定的理论价值，但是对于一般形式单圈图H（p，pK1，m）的Laplacian谱确定问题还没有解决，有待继续研究。