图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）也分别由其拉普拉斯谱确定。

前述