树的谱矩研究

吴亚平，吕康南，付 捷

（江汉大学 数学与计算机科学学院，湖北 武汉 430056）

0 引言

1942年Kelly和 Ulam提出重构猜想［1］。重构猜想是图论的三大著名难题之一。至今关于重构猜想是否是NP-C问题仍无定论。在对重构猜想的研究中，其中涉及的一个问题是：找出图的不变量的完全组，即找出一组特性或参数，可由它们完全确定一个图。目前对图提出了许多参数，如：连通度、点独立数、色数、最长路长、最短圈长、最大匹配的边数、阶、度序列、最大度、最小度等等。但图的不变量的完全组的确定仍在探讨中。图的k阶谱矩等于图中长为k的闭途径的条数，可知谱矩序列也是图的一个很重要的不变量。因此图的谱矩序列的确定，对研究重构猜想是有意义的。

猜想［1］（重构猜想）如果G是至少有3个顶点的简单图，则G由它的顶点删除子图（的同构类）序列唯一确定。

20世纪以来，图的排序问题成为代数图论中比较有趣的问题之一。1987年，Cvetkovíc和Rowlinson［2］给出图的前4阶谱矩的计算公式，同时给出树和单圈图依谱矩序排在最前和最后的图。2009年范琼等［3］给出图的第5阶和第6阶谱矩的计算公式。2010年吴亚平等［4］给出给定直径的树依谱矩序排在前[d +12]的图，这里d为给定树的直径。2011年Pan X F等［5］给出给定最大度的树谱矩序排序。2012年Pan X F等［6］研究1-伪树图谱矩序排序。本文将给出树的前8阶谱矩的计算公式。

1 预备知识

本文只考虑简单图，文中出现而未介绍的定义参照文献［1］。设 G=(V(G)，E(G))，其中V(G)是G的顶点集，E(G)是G的边集。G的一条(v0，vk)-途径W 是由G中顶点和边构成的一个序列 v0，e1，v1，e2，…ek，vk，使得对于1≤i≤k，边 ei的两个端点为 vi-1和 vi。若W 的每个顶点互不相同，则称它为一条(v0，vk)-路。如果v0=vk，则称W是一条闭途径。若W是一条闭途径且它的每个顶点互不相同，则称W是一个圈。途径、圈或路的长度是指其中边的数目。令Pk+1、Ck分别表示长为k的路和圈。连通无圈图称为树。星树是一棵树，并且它只有一个顶点邻接于其他所有顶点，这个顶点称为星树的中心点。n-顶点星树记为K1，n-1。

n阶图G的邻接矩阵 A(G)=[aij]n×n，其中aij=1，如果顶点vi与顶点 vj相邻；否则 aij=0（i，j=1，2，…，n）。 A(G)的特征值即为图G 的特征值。由于A(G)是n阶实对称矩阵，所以其n个特征值 λ1(G )，λ2(G )，…，λn(G)均为实数，图G

的n个特征值的k次幂之和称为图G的第k阶谱矩，记为Sk(G)(k=0，1，…，n)。由此得到图G的谱矩序列S=(S0(G)，S1(G )，…，Sn(G))。

引理2［2］图G的第k阶谱矩等于G中长为k的闭途径的个数。

引理3［2］设G是n阶图，则

其中l、m、t分别表示图中环、边、三角形的个数，p、q分别表示相邻边对和四边形的个数。

引理4［3］设G是n阶图，则

其中 ci表示 G 中圈 Ci的个数（i=3，4，5，6）；pi表示 G 中路 Pi的个数（i=2，3，4）；k1，3表示 G中星树 K1，3的个数；分别表示G中带一个悬挂点的3圈子图和带一个悬挂点的4圈子图的个数；a3，3表示G中2圈长为3且有一个公共点的5阶双圈图A5(3 ，3) 的个数；b3，3表示 G 中2圈长为3且有一条公共边的4阶双圈图B4(3 ，3)的个数。

引理5［3］设T是一棵 n阶树，则T中长为i=2 k的闭途径只可能存在于T中阶数不超过k的所有子图中。

2 主要结果

根据引理1-5可知，n阶树T的任意奇数阶谱矩皆为0，前6阶偶数阶谱矩为：

下面给出树第8阶谱矩计算公式。

定理1 设T是n阶树，则

其中 pj表示 T 中路子图 Pj（ j=2，3，4，5）的个数；k1，3表示 T 中星树 K1，3的个数；k1，4表示 T 中星树 K1，4的个数。

证明 根据引理2，树的第8阶谱矩等于树中长为8的闭途径的条数。

由引理5可以得到，树中长为8的闭途径仅存在于以下树子图中（见图1）：

图1 阶数小于6的非平凡树

下面分别计算它们产生长为8不同的闭途径的条数。

将P2左右两点分别标记为a、b。从两顶点出发各有一条长为8的闭途径，分别为：ababababa、babababab，共2条。

将P3左右两点分别标记为a、c，中间点标记为b。从a点出发有7条长为8的闭途径，分别为：abababcba、ababcbaba、ababcbcba、abcbababa、abcbabcba、abcbcbcba、abcbcbaba，从c点出发同样有7条长为8的闭途径。

从b点出发第一条边为ba的长为8闭途径：babababcb、bababcbab、bababcbcb、babcbabab、babcbabcb、babcbcbab、babcbcbcb。同理，从b点出发，若第一条边为bc的长为8闭途径也有7条，即从b点出发的长为8闭途径共有14条。因此从a、b、c三顶点出发长为8闭途经共有28条。

将P4的顶点从左到右依次标记为a、b、c、d。从a点出发的长为8闭途径有：ababcdcba、abcbcdcba、abcdcbaba、abcdcbcba、abcdcd cba。同理从d点出发也有5条；从b点出发的长为8闭途径有：bababcdcb、babcbcdcb、babcdcbab、babcdcbcb、babcdcdcb、bcbabcdcb、bcbcdcbab、bcdcbabab、bcdcbabcb、bcdcbcbab、bcdcdcbab 。同理从c点出发也有11条。所以共有32条长为8闭途径。

将 P5从左到右依次标记为 a、b、c、d、e。从a、e两点出发的长为8闭途径各有一条，从b、c、d点出发的长为8闭途径各有2条，分别 是 ：babcdedcb、bcdedcbab；cbabcdedc、cdedcbabc；dedcbabcd、dcbabcded。所以共有8条长为8闭途径。

将K1，3的中心点标记为a，其他点从左到右依次标记为b、c、d。从a点出发第一条边为ab的长为8闭途径有：ababacada、ababadaca、abacabada、abacacada、abacadaba、abacadaca、abacadada、abadabaca、abadacaba、abadacaca、abadacada、abadadaca；同理，若第一条边为ac或ad也有12条长为8闭途径。

从b点出发第二条边为ab的长为8闭途径有：babacadab、babadacab；从b点出发第二条边为ac的长为8闭途径有：bacabadab、bacacadab、bacadabab、bacadacab、bacadadab；同理，第二条边为ad同样有5条长为8闭途径。所以共有72条长为8闭途径。

将K1，4的中心点标记为a，其他点从左到右依次标记为b、c、d、e。因为k1，4是树图，每条边必须走两次。根据排列组合原理，从a点出发的长为8闭途径有：··=24；从b点出发的长为8闭途径有：bacadaeab、bacaeadab、badacaeab、badaeacab、baeacadab、baeadacab；同理，从c、d、e出发同样有6条。所以共有48条。

［1］West D B.图论导引：英文版［M］.2版.北京：机械工业出版社，2004.

［2］Cvetkovíc D，Rowlinson P.Spectra of unicyclic graphs［J］.Graph and Combinatorics，1987（3）：7-23.

［3］范琼，吴亚平.图的谱矩序列与图的排序［J］.武汉大学学报：理学版，2009，55（6）：1-4.

［4］Wu Y P，Liu H Q.Lexicographical ordering by spectral moments of trees with a prescribed diameter［J］.Linear Algebra and Its Application，2010，433（11/12）：1707-1713.

［5］Pan X F，Hu X L，Liu X G，et al.The spectral mo⁃ments of trees with given maximum degree［J］.Applied Mathematics Letters，2011，24：1265-1268.

［6］Pan X F，Liu X G，Liu H Q.On the spectral moment of quasi-trees［J］.Linear Algebra and Its Applications，2012，436：927-934.