单圈图H(p,2K1,6)的拉普拉斯谱刻画

赵绍玉

(三明学院 信息工程学院,福建 三明 365004)

这里考虑的是连通的简单无向图。令V(G)表示图G的顶点集,E(G)表示其边集,ni(G)表示G中度为i的顶点数,A(G)=(aij)n×n表示其邻接矩阵,当vi和vj在图G中相邻时,aij等于1,否则为0.di表示图G中顶点vi的度数。D(G)=diag(d1,d2,…,dn)是由G中顶点的度构成的对角矩阵。矩、阵L(G)=D(G)-A(G)称为图G的拉普拉斯矩阵。多项式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的拉普拉斯特征多项式,In是单位矩阵。设λi(i=1,…,n)是A(G)的特征值,它们的集合构成了图G的邻接谱;μi(i=1,…,n)是L(G)的特征值,它们构成的集合称为图G的拉普拉斯谱。如果两个图的邻接谱是相同的,就称它们是邻接同谱图。同样,若两个图的拉普拉斯谱相同,则称它们是拉普拉斯同谱图。若与图G邻接同谱的图都与G同构,称图G可由其邻接谱确定。同样,若与图G拉普拉斯同谱的图都与G同构,称图G可由其拉普拉斯谱确定。由于化学研究的需要,Günthard和Primas[1]在1956年提出了图谱的确定问题;到了2003年,这一问题再次被Van Dam 和Haemers[2]提出,引起了广泛的关注,陆续出现了很多研究成果,具体可参见文献[3]。用H(p,tK1,m)表示具有tm+p个顶点的单圈图,它是由圈Cp连续相邻的t(1≤t≤p)个顶点分别与星K1,m的中心重合而得到的。卢鹏丽[4]证明了图H(p,K1,m)是由它的拉普拉斯谱确定的;Bu等[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]证明了单圈图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)也分别由其拉普拉斯谱确定。赵绍玉[9]证明了单圈图H(p,pK1,6)是由其拉普拉斯谱确定的。对于单圈图H(p,2K1,6)和H(p,pK1,m)(m>6)的拉普拉斯谱确定问题还没有具体研究结果。本文证明了当p为偶数时,单圈图H(p,2K1,6)(m>6)也是由它的拉普拉斯谱确定。

1 基本引理

引理1[3]若两个图是拉普拉斯同谱图,则它们的顶点数和边数相同;并且两图所有顶点度的平方和相等;若两个图是邻接同谱图,则它们具有相同的顶点数、边数和任意长度的闭回路数。

引理2[10]设连通图G是含有圈Ck的单圈图。若图G′与图G具有相同的拉普拉斯谱,则图G′也是含有圈Ck的连通单圈图,并且

引理3[11]令Δ表示图G的最大的顶点度,mi表示图G中与顶点vi邻接的顶点的度数的平均值。则有

引理4[7]若两个二部图G和H是拉普拉斯同谱图,则它们所对应的线图l(G)和l(H)是邻接同谱的。

引理5[7]任意简单图的长度为4的闭合回路数等于其边数的2倍加上长度为2的诱导路数的4倍再加上8倍的长度为4圈的数目。

2 主要结果

定理当p为偶数时,图G=H(p,2K1,6)由其拉普拉斯谱确定。

证明:假设图G和图G′是拉普拉斯谱的,则由引理1可知,图G′是一个具有p+12个顶点,p+12条边且含有圈Cp的连通单圈图。由引理3得

所以Δ≤9。

设ni是图G中度为i的顶点个数。由引理1和引理2知

解上述方程组得

n1=35n9-28+n5+4n6+10n7+20n8,

n2=p+138-120n9-4n5-15n6-36n7-70n8,

n3=140n9-168+6n5+20n6+45n7+84n8,

n4=70-56n9-4n5-10n6-20n7-35n8。

由引理2知图G′含有圈Cp,所以有

由此推出

n1=n5+4n6+10n7+20n8+35n9-28≤12。

由ni≥0(i=2,3,4)可得

n5+4n6+10n7+20n8+35n9≤40,

(1)

4n5+15n6+36n7+70n8+120n9≤p+138,

(2)

6n5+20n6+45n7+84n8+140n9≥168,

(3)

4n5+10n6+20n7+35n8+56n9≤70。

(4)

由(1)×6-(3)得

4n6+15n7+36n8+70n9≤72。

(5)

由(2)×3-(3)×2得

5n6+18n7+42n8+80n9≤p+78。

(6)

由(3)×2-(4)×3得

10n6+30n7+63n8+112n9≥126。

(7)

由(5)×5-(7)×2得

5n7+18n8+42n9≤36。

(8)

因为n9≥0为整数且p为大于3的任意偶数,所以由(8)得到n9=0,n8≤2.针对n8≤2,分下面3种情况进行讨论。

情况1若n8=2,代入(1)可得:n7=n6=n5=0,进而推出n2=p-2,n3=n4=0,n1=12.此种情况成立。

情况2若n8=1,代入(4)可得:n7≤1,若n7=1,代入(7),可推得n6≥3.3,再代入(4)得到矛盾。若n7=0,代入(7),可推得n6≥6.3,同样代入(4)得到矛盾。所以综合两种情况,情况n8=1不成立。

情况3若n8=0,代入(4)可得:n7≤3.5,因为ni(i=1,…,9)是大于等于0的正整数,所以讨论如下。

若n7=3,代入(4),可推得n6≤1。若n6=1,代入(4),可推得n5=0,再代入(3)得到矛盾。若n6=0,同n6=1的讨论也得到矛盾。所以在n8=0的情况下n7=3这种情形不成立。n7=2的情形讨论同n7=3,可以推出也不成立.若n7=1,代入(7),可推得n6≥9.6,同样代入(4)得到矛盾。n7=0的情形讨论同n7=1也可得到矛盾。所以综合以上讨论,可知n8=0的情况也不成立。

综合以上3种情况,可知只有n8=2的情况成立,此时图G′的度序列为d(G′)=(82,2p-2,112)。而含有圈Cp且度序列为(82,2p-2,112)的连通单圈图只能是形如H(p,2K1,6)的图,但是图G′的两个2度点在圈Cp上的位置可能相邻,也可能不相邻,所以讨论如下:

情况1若图G′两个2度点的位置在圈Cp上相邻,则G′≅G。

情况2若图G′两个2度点的位置在圈Cp上相邻不相邻,因为p为大于3的偶数,所以图G′和G都是二部图。由引理4可知图G′和G的线图l(G′)和l(G)具有相同的邻接谱。借助引理1可知线图l(G′)和l(G)具有相同数目长度为4的闭回路。再由引理1和引理5可知线图l(G′)和l(G)中长度为2的诱导路的个数也是相同的。线图l(G′)的度序列为(84,712,2p-4),l(G)的度序列为(141,82,712,2p-3),由此推出

得到矛盾,所以此种情况不成立。

综上所述,图G′中两个2度点的位置在圈Cp上相邻,此种情况G′≅G,即当p为偶数时,图G=H(p,2K1,6)是由其拉普拉斯谱确定的。

3 结语

本文在一定条件下,借助图与它的补图之间的关系和拉普拉斯同谱图的一些性质,证明了单圈图H(p,2K1,6)由它的拉普拉斯谱确定。对于单圈图H(p,tK1,m)(t>1,m>6)的情形还没有研究,有兴趣的读者可以继续讨论下去。