吳亞平，呂康南，付 捷

（江漢大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，湖北 武漢 430056）

0 引言

1942年Kelly和 Ulam提出重構(gòu)猜想［1］。重構(gòu)猜想是圖論的三大著名難題之一。至今關(guān)于重構(gòu)猜想是否是NP-C問題仍無定論。在對重構(gòu)猜想的研究中，其中涉及的一個問題是：找出圖的不變量的完全組，即找出一組特性或參數(shù)，可由它們完全確定一個圖。目前對圖提出了許多參數(shù)，如：連通度、點獨立數(shù)、色數(shù)、最長路長、最短圈長、最大匹配的邊數(shù)、階、度序列、最大度、最小度等等。但圖的不變量的完全組的確定仍在探討中。圖的k階譜矩等于圖中長為k的閉途徑的條數(shù)，可知譜矩序列也是圖的一個很重要的不變量。因此圖的譜矩序列的確定，對研究重構(gòu)猜想是有意義的。

猜想［1］（重構(gòu)猜想）如果G是至少有3個頂點的簡單圖，則G由它的頂點刪除子圖（的同構(gòu)類）序列唯一確定。

20世紀(jì)以來，圖的排序問題成為代數(shù)圖論中比較有趣的問題之一。1987年，Cvetkovíc和Rowlinson［2］給出圖的前4階譜矩的計算公式，同時給出樹和單圈圖依譜矩序排在最前和最后的圖。2009年范瓊等［3］給出圖的第5階和第6階譜矩的計算公式。2010年吳亞平等［4］給出給定直徑的樹依譜矩序排在前[d +12]的圖，這里d為給定樹的直徑。2011年P(guān)an X F等［5］給出給定最大度的樹譜矩序排序。2012年P(guān)an X F等［6］研究1-偽樹圖譜矩序排序。本文將給出樹的前8階譜矩的計算公式。

1 預(yù)備知識

本文只考慮簡單圖，文中出現(xiàn)而未介紹的定義參照文獻［1］。設(shè) G=(V(G)，E(G))，其中V(G)是G的頂點集，E(G)是G的邊集。G的一條(v0，vk)-途徑W 是由G中頂點和邊構(gòu)成的一個序列 v0，e1，v1，e2，…ek，vk，使得對于1≤i≤k，邊 ei的兩個端點為 vi-1和 vi。若W 的每個頂點互不相同，則稱它為一條(v0，vk)-路。如果v0=vk，則稱W是一條閉途徑。若W是一條閉途徑且它的每個頂點互不相同，則稱W是一個圈。途徑、圈或路的長度是指其中邊的數(shù)目。令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)均為實數(shù)，圖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的閉途徑的個數(shù)。

引理3［2］設(shè)G是n階圖，則

其中l(wèi)、m、t分別表示圖中環(huán)、邊、三角形的個數(shù)，p、q分別表示相鄰邊對和四邊形的個數(shù)。

引理4［3］設(shè)G是n階圖，則

其中 ci表示 G 中圈 Ci的個數(shù)（i=3，4，5，6）；pi表示 G 中路 Pi的個數(shù)（i=2，3，4）；k1，3表示 G中星樹 K1，3的個數(shù)；分別表示G中帶一個懸掛點的3圈子圖和帶一個懸掛點的4圈子圖的個數(shù)；a3，3表示G中2圈長為3且有一個公共點的5階雙圈圖A5(3 ，3) 的個數(shù)；b3，3表示 G 中2圈長為3且有一條公共邊的4階雙圈圖B4(3 ，3)的個數(shù)。

引理5［3］設(shè)T是一棵 n階樹，則T中長為i=2 k的閉途徑只可能存在于T中階數(shù)不超過k的所有子圖中。

2 主要結(jié)果

根據(jù)引理1-5可知，n階樹T的任意奇數(shù)階譜矩皆為0，前6階偶數(shù)階譜矩為：

下面給出樹第8階譜矩計算公式。

定理1 設(shè)T是n階樹，則

其中 pj表示 T 中路子圖 Pj（ j=2，3，4，5）的個數(shù)；k1，3表示 T 中星樹 K1，3的個數(shù)；k1，4表示 T 中星樹 K1，4的個數(shù)。

證明 根據(jù)引理2，樹的第8階譜矩等于樹中長為8的閉途徑的條數(shù)。

由引理5可以得到，樹中長為8的閉途徑僅存在于以下樹子圖中（見圖1）：

圖1 階數(shù)小于6的非平凡樹

下面分別計算它們產(chǎn)生長為8不同的閉途徑的條數(shù)。

將P2左右兩點分別標(biāo)記為a、b。從兩頂點出發(fā)各有一條長為8的閉途徑，分別為：ababababa、babababab，共2條。

將P3左右兩點分別標(biāo)記為a、c，中間點標(biāo)記為b。從a點出發(fā)有7條長為8的閉途徑，分別為：abababcba、ababcbaba、ababcbcba、abcbababa、abcbabcba、abcbcbcba、abcbcbaba，從c點出發(fā)同樣有7條長為8的閉途徑。

從b點出發(fā)第一條邊為ba的長為8閉途徑：babababcb、bababcbab、bababcbcb、babcbabab、babcbabcb、babcbcbab、babcbcbcb。同理，從b點出發(fā)，若第一條邊為bc的長為8閉途徑也有7條，即從b點出發(fā)的長為8閉途徑共有14條。因此從a、b、c三頂點出發(fā)長為8閉途經(jīng)共有28條。

將P4的頂點從左到右依次標(biāo)記為a、b、c、d。從a點出發(fā)的長為8閉途徑有：ababcdcba、abcbcdcba、abcdcbaba、abcdcbcba、abcdcd cba。同理從d點出發(fā)也有5條；從b點出發(fā)的長為8閉途徑有：bababcdcb、babcbcdcb、babcdcbab、babcdcbcb、babcdcdcb、bcbabcdcb、bcbcdcbab、bcdcbabab、bcdcbabcb、bcdcbcbab、bcdcdcbab 。同理從c點出發(fā)也有11條。所以共有32條長為8閉途徑。

將 P5從左到右依次標(biāo)記為 a、b、c、d、e。從a、e兩點出發(fā)的長為8閉途徑各有一條，從b、c、d點出發(fā)的長為8閉途徑各有2條，分別 是 ：babcdedcb、bcdedcbab；cbabcdedc、cdedcbabc；dedcbabcd、dcbabcded。所以共有8條長為8閉途徑。

將K1，3的中心點標(biāo)記為a，其他點從左到右依次標(biāo)記為b、c、d。從a點出發(fā)第一條邊為ab的長為8閉途徑有：ababacada、ababadaca、abacabada、abacacada、abacadaba、abacadaca、abacadada、abadabaca、abadacaba、abadacaca、abadacada、abadadaca；同理，若第一條邊為ac或ad也有12條長為8閉途徑。

從b點出發(fā)第二條邊為ab的長為8閉途徑有：babacadab、babadacab；從b點出發(fā)第二條邊為ac的長為8閉途徑有：bacabadab、bacacadab、bacadabab、bacadacab、bacadadab；同理，第二條邊為ad同樣有5條長為8閉途徑。所以共有72條長為8閉途徑。

將K1，4的中心點標(biāo)記為a，其他點從左到右依次標(biāo)記為b、c、d、e。因為k1，4是樹圖，每條邊必須走兩次。根據(jù)排列組合原理，從a點出發(fā)的長為8閉途徑有：··=24；從b點出發(fā)的長為8閉途徑有：bacadaeab、bacaeadab、badacaeab、badaeacab、baeacadab、baeadacab；同理，從c、d、e出發(fā)同樣有6條。所以共有48條。

［1］West D B.圖論導(dǎo)引：英文版［M］.2版.北京：機械工業(yè)出版社，2004.

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

［3］范瓊，吳亞平.圖的譜矩序列與圖的排序［J］.武漢大學(xué)學(xué)報：理學(xué)版，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.