几乎完全图是由第二Immanantal多项式刻画的①

曾晓琳， 吴廷增， 潘佳丽

青海民族大学 数学与统计学院，西宁 810007

其中χ表示Sn关于划分(2,1,…,1)的不可约特征标.令G是一个含有n个顶点的图,L(G)表示图G的拉普拉斯矩阵.多项式d2(xI-L(G))表示图G的第二imamnantal多项式,其中I表示n阶单位矩阵.本文证明了几乎完全图是由第二imamnantal多项式确定的．

一个n阶矩阵A=(aij)(i,j∈{1,2,…,n})的第二immanant定义为

其中χ是Sn关于划分(2,1,…,1)的不可约特征标.特别地,χ(σ)=ε(σ)[F(σ)-1],其中ε是交替特征标,F是固定点的个数．

第二immanant是积和式与行列式之间的一个不变量.文献[1]指出计算第二immanant的时间复杂度是n4.假设矩阵A的阶为n(≥2),因为d2(A)的项对应于detA的因子(F(σ)-1)(σ∈Sn).因此有

(1)

其中A(i)是删除矩阵A的第i行和第i列得到的子矩阵.例如,假设

根据公式(1),可得d2(A)=18．

令G是含有n个顶点的图.A(G)是图G的(0,1)-邻接矩阵.di表示顶点vi的度.矩阵

L(G)=D(G)-A(G)

称为图G的拉普拉斯矩阵,其中D(G)是对角元素为{d1,d2,…,dn}的n阶度矩阵．

多项式

称作图G的第二immanantal多项式,记作d2-多项式,其中I是n×n单位矩阵.为了强调图G,系数通常记作ck(G)(0≤k≤n)．

两个图是共第二immanant的,是指这两个图分享相同的第二immanantal多项式.图H与图G是共第二immanant的,但不是同构的,则称H是G的一个共第二immanant伙伴.如果图G没有共第二immanant伙伴,则称图G是由第二immanantal多项式确定的．

图谱理论中的一个经典问题: 什么样的图是由多项式确定的?在图多项式理论中,这是一个困难的问题.近几年,这个问题受到了许多学者的关注.一些图G已经被证明是由矩阵(xI-L(G))的行列式确定的,例如双星状图[2]、沙漏图[3]、Zn图[4]、T-形树[5]、∞-图[6]等．

最近,学者们考虑了什么样的图是由矩阵(xI-L(G))的积和式确定的.文献[7]证明了完全图和圈是由矩阵(xI-L(G))的积和式确定的.文献[8]证明了棒棒糖图是由(xI-L(G))的积和式确定的.关于这个问题更多的研究,可参见文献[9-18]．

文献[19]首次考虑了一个问题: 什么样的图是由d2-多项式确定的? 文献[19]证明了: 几乎所有的树都有共第二immanant伙伴.特别地,文献[1]证明了: 如果图G和H是两个正则图,则G和H是共第二immanant的当且当

det(xI-L(G))=det(xI-L(H))

或

det(xI-A(G))=det(xI-A(H))

并且,文献[10]发现一对非正则的图对是共第二immanant的,如图1所示．

图1 非正则的且共第二immanant的图对

基于文献[19]的探讨,存在一个有趣的问题: 寻找一些图,既是由d2-多项式确定的,也是由特征多项式det(xI-A(G))确定的.本文围绕这个问题开展研究．

令Gn是从完全图Kn删除至多5条边得到的图集.文献[20]证明了Gn中所有的图都是由其特征多项式确定的.本文讨论Gn中哪些图是由其第二immanantal多项式确定的.意外的是,我们发现,无例外地,Gn中所有的图都是由其第二imamnantal多项式确定的．

定理1Gn中所有的图都是由其第二immanantal多项式确定的．

本文剩余内容的结构如下: 先给出一些d2-多项式的性质; 再给出定理1的证明; 最后提出两个值得未来进一步研究的有意义的问题．

令图G=(V,E)表示一个含有非空点集V和非空边集E的无向简单图,即G是不含有环和重边的图．

文献[21]指出,对n≥10,在Gn中存在45个非同构图,并标记为Gij(i=1,2,…,5;j=0,1,…,25),如图2所示．

图2 从完全图Kn中删除至多5条边得到的图集Gn

引理1[1]令G是含有n个顶点和m条边的连通图,(d1,d2,…,dn)表示图G的度序列,L(G)是图G的拉普拉斯矩阵,且

则

c0(G)=n-1

c1(G)=2m(n-1)

cn(G)=2mτ(G)

其中τ(G)表示图G的生成树的个数．

由引理1,我们可以得到d2-多项式的一些性质．

引理2从图G的d2-多项式的系数c0(G),c1(G)和cn(G)可以推断出G的顶点数、边数、生成树的个数．

其中τ(G)是G的生成树的个数．

由引理3,我们计算出了Gn中一些图的生成树的个数,如表1所示．

表1 Gn中图的生成树的个数

由引理3,我们可得:

定理2图G10是由d2-多项式确定的．

定理3图G20和G21是由d2-多项式确定的．

证根据表1,我们知道

τ(G20)-τ(G21)=nn-4(n2-4n+3)-nn-4(n2-4n+4)≠0

由引理2可知,这意味着G20和G21是由d2-多项式确定的．

定理4图G30,G31,G32,G33和G34是由d2-多项式确定的．

证根据G3i(i=0,1,…,4)的图结构,我们知道

|V(G30)|≥4 |V(G31)|≥5 |V(G32)|≥3 |V(G33)|≥4 |V(G34)|≥6

与定理3类似,根据表1可得,只有当n=4时,

τ(G32)-τ(G33)=(-n+4)nn-5=0

根据引理1,我们可以得到

c2(G32)=33c2(G33)=36

这意味着G32和G33不是共第二immanant的．

同样地,解方程

τ(G30)-τ(G31)=nn-5(-2n+2)=0

τ(G31)-τ(G32)=(2n-6)nn-5=0

τ(G31)-τ(G33)=(n-2)nn-5=0

τ(G31)-τ(G34)=(2-n)nn-5=0

τ(G33)-τ(G34)=(-2n+4)nn-5=0

我们得到这些方程的解n小于对应图的顶点数,矛盾.所以,G31和G33,G31和G34,G33和G34分别都不是共第二immanant的．

由表1,解方程

τ(G30)-τ(G32)=0τ(G30)-τ(G33)=0

τ(G30)-τ(G34)=0τ(G32)-τ(G34)=0

可以得出这些方程或者没有解,或者没有整数解．

由引理2及以上的讨论可知,图G30,G31,G32,G33和G34是由d2-多项式确定的．

定理5图G40,G41,G42,G43,G44,G45,G46,G47,G48,G49和G4(10)是由d2-多项式确定的．

证根据图G4j(j=0,1,…,10)的结构,我们可以得到|V(G40)|≥5,|V(G41)|≥6,|V(G42)|≥6,|V(G43)|≥7,|V(G44)|≥4,|V(G45)|≥5,|V(G46)|≥4,|V(G47)|≥5,|V(G48)|≥6,|V(G49)|≥8和|V(G4(10))|≥5．

由表1得到,只有当n=4时,τ(G44)-τ(G46)=(n-4)nn-5=0.如果n=4,由引理1,我们得到c2(G44)=16和c2(G46)=14.这表明G44和G46不是共第二immanant的．

同样地,只有当n=-1,5时,有τ(G44)-τ(G47)=(-n2+4n-5)nn-6=0.如果n=5,由引理1可知,在图G44和G47中,c2(G44)=212和c2(G47)=216.这意味着G44和G47不是共第二immanant的．

类似地,只有当n=1,5时,τ(G46)-τ(G4(10))=(-n2+6n-5)nn-6=0.如果n=5,由引理1可得,c2(G46)=208和c2(G4(10))=212.这说明G46和G4(10)不是共第二immanant的．

根据表1,解方程τ(G40)-τ(G4j)=0(j=1,2,3,5,6,10),τ(G41)-τ(G4j)=0(j=2,3,4,5,6,8,9,10),τ(G42)-τ(G4j)=0(j=3,5,6,7,8,10),τ(G43)-τ(G4j)=0(j=4,5,6,8,9,10),τ(G44)-τ(G4j)=0(j=5,8,9),τ(G45)-τ(G4j)=0(j=8,9),τ(G47)-τ(G4j)=0(j=8,10),τ(G48)-τ(G49)=0.我们得到这些方程的根n小于对应图的顶点数,矛盾.因此,图G40和图G41,G42,G43,G45,G46,G4(10); 图G41和图G42,G43,G44,G45,G46,G48,G49,G4(10); 图G42和图G43,G45,G46,G47,G48,G4(10); 图G43和图G44,G45,G46,G49,G4(10); 图G44和图G45,G48,G49; 图G45和图G48,G49; 图G47和图G48,G4(10); 图G48和图G49都分别不是共第二immanant的．

由表1,解方程τ(G40)-τ(G4j)=0(j=4,7,8,9),τ(G41)-τ(G47)=0,τ(G42)-τ(G4j)=0(j=4,9),τ(G43)-τ(G47)=0,τ(G44)-τ(G4(10))=0,τ(G45)-τ(G4j)=0(j=6,7,10),τ(G46)-τ(G4j)=0(j=7,8,9),τ(G47)-τ(G49)=0,τ(G48)-τ(G4(10))=0和τ(G49)-τ(G4(10))=0.我们可以得出这些方程或者没有解,或者没有整数根.这说明G40和G44,G47,G48,G49;G41和G47;G42和G44,G49;G43和G47;G44和G4(10);G45和G46,G47,G4(10);G46和G47G48,G49;G47和G49;G48和G4(10);G49和G4(10)都分别不是共第二immanant的．

根据引理2和上述讨论可得,G40,G41,G42,G43,G44,G45,G46,G47,G48,G49和G4(10)是由d2-多项式确定的．

定理6图G50,G51,G52,G53,G54,G55,G56,G57,G58,G59,G5(10),G5(11),G5(12),G5(13),G5(14),G5(15),G5(16),G5(17),G5(18),G5(19),G5(20),G5(21),G5(22),G5(23),G5(24)和G5(25)是由d2-多项式确定的．

证根据图G5j(j=0,1,…,25)的结构,我们可得|V(G50)|≥8,|V(G51)|≥8,|V(G52)|≥9,|V(G53)|≥7,|V(G54)|≥6,|V(G55)|≥6,|V(G56)|≥7,|V(G57)|≥7,|V(G58)|≥8,|V(G59)|≥5, |V(G5(10))|≥5,|V(G5(11))|≥7,|V(G5(12))|≥5,|V(G5(13))|≥6,|V(G5(14))|≥7,|V(G5(15))|≥5,|V(G5(16))|≥4,|V(G5(17))|≥7,|V(G5(18))|≥6,|V(G5(19))|≥6,|V(G5(20))|≥5,|V(G5(21))|≥10,|V(G5(22))|≥6,|V(G5(23))|≥6,|V(G5(24))|≥6和|V(G5(25))|≥6．

与定理5的证明类似,根据表1可得:

只有当n=1,n=6时,τ(G59)-τ(G5(24))=nn-7(-n3+8n2-13n+6)=0.如果n=6,由引理1可得c2(G59)=780和c2(G5(24))=790.这表明G59和G5(24)不是共第二immanant的．

只有当n=1,n=5时,τ(G5(10))-τ(G5(15))=nn-6(-n2+6n-5)=0.类似地,如果n=5,根据引理1可得c2(G5(10))=106和c2(G5(15))=146.这说明G5(10)和G5(15)不是共第二immanant的．

只有当n=3,n=5时,τ(G5(10))-τ(G5(16))=nn-6(n2-8n+15)=0 .如果n=5,由引理1得到c2(G5(10))=106和c2(G5(16))=138.这意味着G5(10)和G5(16)不是共第二immanant的．

只有当n=2,5时,τ(G5(15))-τ(G5(16))=nn-6(2n2-14n+20)=0.如果n=5,根据引理1可得c2(G5(15))=146和c2(G5(16))=138.这说明G5(15)和G5(16)不是共第二immanant的．

只有当n=-1,5时,τ(G5(15))-τ(G5(20))=nn-6(-n2+4n-5)=0.如果n=5时,由引理1得到c2(G5(15))=146和c2(G5(20))=150.这表明G5(15)和G5(20)不是共第二immanant的．

类似地,根据表1,解方程τ(G50)-τ(G5j)=0(j=1,2,3,6,8,11,14,15,…,23),τ(G51)-τ(G5j)=0(j=1,10,20),τ(G52)-τ(G5j)=0(j=1,2,10,20),τ(G53)-τ(G5j)=0(j=1,2,3,10,12,13,20),τ(G54)-τ(G5j)=0(j=5,6,7,8,11,13,18,22,24,25),τ(G55)-τ(G5j)=0(j=6,7,8,9,11,12,13,18,20,22,23,24,25),τ(G56)-τ(G5j)=0(j=7,8,9,11,13,15,16,17,18,19,21,22,23,24,25),τ(G57)-τ(G5j)=0(j=8,10,11,12,13,14,17,18,19,20,22,24,25),τ(G58)-τ(G5j)=0(j=9,11,13,14,…,19,21,22,23,24,25),τ(G59)-τ(G5j)=0(j=10,11,12,13,14,18,22,25),τ(G5(10))-τ(G5j)=0(j=12,21,23),τ(G5(11))-τ(G5j)=0(j=12,13,14,…,19,21,22,23,24,25),τ(G5(12))-τ(G5j)=0(j=13,14,18,22,25),τ(G5(13))-τ(G5j)=0(j=14,18,22,24,25),τ(G5(14))-τ(G5j)=0(j=15,16,17,18,19,21,22,23,25),τ(G5(15))-τ(G5j)=0(j=17,18,19,21,22,23),τ(G5(16))-τ(G5j)=0(j=17,18,19,21,22,23),τ(G5(17))-τ(G5j)=0(j=18,19,…,23),τ(G5(18))-τ(G5j)=0(j=19,20,…,25),τ(G5(19))-τ(G5j)=0(j=21,22,23),τ(G5(20))-τ(G5(24))=0,τ(G5(21))-τ(G5j)=0(j=22,23),τ(G5(22))-τ(G5j)=0(j=23,24,25})和τ(G5(24))-τ(G5(25))=0.我们得到这些方程的根n小于对应图的顶点数,矛盾.因此,G50和G5j(j=1,2,3,6,8,11,14,15,…,23),G51和G5j(j=1,10,20),G52和G5j(j=1,2,10,20),G53和G5j(j=1,2,3,10,12,13,20),G54和G5j(j=5,6,7,8,11,13,18,22,24,25),G55和G5j(j=6,7,8,9,11,12,13,18,20,22,23,24,25),G56和G5j(j=7,8,9,11,13,15,16,17,18,19,21,22,23,24,25),G57和G5j(j= 8,10,11,12,13,14,17,18,19,20,22,24,25),G58和G5j(j=11,13,14,…,19,21,22,23,24,25),G59和G5j(j=10,11,12,13,14,18,22,25),G5(10)和G5j(j=12,21,23),G5(11)和G5j(j=12,13,14,…,19,21,22,23,24,25),G5(12)和G5j(j=13,14,18,22,25),G5(13)和G5j(j=14,18,22,24,25),G5(14)和G5j(j=15,16,17,18,19,21,22,23,25),G5(15)和G5j(j=17,18,19,21,22,23),G5(16)和G5j(j=17,18,19,21,22,23),G5(17)和G5j(j=18,19,…,23),G5(18)和G5j(j=19,20,…,25),G5(19)和G5j(j=21,22,23),G5(20)和G5(24),G5(21)和G5j(j=22,23),G5(22)和G5j(j=23,24,25),G5(24)和G5(25)都分别不是共第二immanant的．

同样地,根据表1,解方程τ(G50)-τ(G5j)=0(j=4,5,7,9,10,12,13,24,25),τ(G51)-τ(G5j)=0(j=10,20),τ(G52)-τ(G5j)=0(j=10,20),τ(G53)-τ(G5j)=0(j=10,12,13,20),τ(G54)-τ(G5j)=0(j= 9,10,12,14,15,16,17,19,20,21,23),τ(G55)-τ(G5j)=0(j=10,14,15,16,17,19,21),τ(G56)-τ(G5j)=0(j=10,12,14,20),τ(G57)-τ(G5j)=0(j=9,15,16,21,23),τ(G58)-τ(G5j)=0(j=10,12,20),τ(G59)-τ(G5j)=0(j=15,16,17,19,20,21,23),τ(G5(10))-τ(G5j)=0(j=11,13,14,17,18,19,20,22,24,25),τ(G5(11))-τ(G5(20))=0,τ(G5(12))-τ(G5j)=0(j=15,16,17,19,20,21,23,24),τ(G5(13))-τ(G5j)=0(j=15,16,17,19,20,21,23),τ(G5(14))-τ(G5j)=0(j=20,24),τ(G5(15))-τ(G5j)=0(j=24,25),τ(G5(16))-τ(G5j)=0(j=20,24,25),τ(G5(17))-τ(G5j))=0(j=24,25),τ(G5(19))-τ(G5j)=0(j= 20,24,25),τ(G5(20))-τ(G5j)=0(j=21,22,23,25),τ(G5(21))-τ(G5j)=0(j=24,25)和τ(G5(23))-τ(G5j)=0(j=24,25).我们可以得到这些方程或者没有解,或者没有整数根.因此,G50和G5j(j=4,5,7,9,10,12,13,24,25),G51和G5j(j=10,20),G52和G5j(j=10,20),G53和G5j(j=10,12,13,20),G54和G5j(j=9,10,12,14,15,16,17,19,20,21,23),G55和G5j(j=10,14,15,16,17,19,21),G56和G5j(j=10,12,14,20),G57和G5j(j=9,15,16,21,23),G58和G5j(j=10,12,20),G59和G5j(j=15,16,17,19,20,21,23),G5(10)和G5j(j=11,13,14,17,18,19,20,22,24,25),G5(11)和G5(20),G5(12)和G5j(j=15,16,17,19,20,21,23,24),G5(13)和G5j(j=15,16,17,19,20,21,23),G5(14)和G5j(j=20,24),G5(15)和G5j(j=24,25),G5(16)和G5j(j=20,24,25),G5(17)和G5j(j=24,25),G5(19)和G5j(j=20,24,25),G5(20)和G5j(j=21,22,23,25),G5(21)和G5j(j=24,25),G5(23)和G5j(j=24,25) 都分别不是共第二immanant的．

由引理2和上述探讨可知,G50,G51,G52,G53,G54,G55,G56,G57,G58,G59,G5(10),G5(11),G5(12),G5(13),G5(14),G5(15),G5(16),G5(17),G5(18),G5(19),G5(20),G5(21),G5(22),G5(23),G5(24)和G5(25)是由d2-多项式确定的．

结合定理2-定理6,定理1得证．

非同构的图有相同的immanantal多项式的例子已经被给了出来.因此,刻画由d2-多项式确定的图是一个有趣的问题.本文证明了所有的几乎完全图都是由d2-多项式确定的.另外,我们发现两个值得进一步研究的问题:

问题2构造一个从完全图Kn中删除l条边得到的图对,使得它们是共第二immanant的．