圖的奇數(shù)階譜矩研究

吳亞平，付 捷，呂康南

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

0 引言

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

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

20 世紀以來，圖的排序問題成為代數(shù)圖論中比較有趣的問題之一。1987 年Cvetkovíc 和Rowlinson［2］給出圖的前4 階譜矩的計算公式，同時給出樹和單圈圖依譜矩序排在最前和最后的圖。2009 年范瓊等［3］給出圖的第5 階和第6 階譜矩的計算公式。2010 年吳亞平等［4］給出給定直徑的樹依譜矩序排在前[d+1/2] 的圖，這里的d 為給定樹的直徑。2011 年Pan 等［5］研究了給定最大度的樹譜矩序排序。2012 年Pan［6］等研究擬樹譜矩序排序。2012 年吳亞平等［7］給出樹的第8 階譜矩計算公式。本文首先確定能生成長為7 的閉途徑的所有子圖，然后給出任一簡單圖的第7 階譜矩計算公式。

1 預備知識

本文中只考慮簡單圖，出現(xiàn)而未介紹的定義可參照文獻［1］。

設G=(V(G)，E(G)) ，其中V(G) 是G 的頂點集，E(G)是G 的邊集。|V( G )|表示G 的頂點數(shù)，|E( G )|表示G 的邊數(shù)。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 是一個圈。途徑、圈或路的長度是指其中邊的數(shù)目。令Pk+1、Ck分別表示長為k 的路和圈。連通無圈圖稱為樹。星樹是一棵樹，并且它有一個頂點鄰接于其他所有頂點。n－頂點星樹記為K1，n-1。連通且恰含有1 個圈的圖稱為單圈圖，連通且恰含有2 個圈的圖稱為雙圈圖。可知，圈Ck是單圈圖，圈Ck中某個頂點與樹T 的某個頂點粘合之后得到的圖也是單圈圖。圈Ck中某個點與圈Cl中某個點粘合之后得到的圖就是一個k+l-1 階雙圈圖，記為Ak+l-1(k，l)，圖中度為1 的點稱為懸掛點。

引理1［2］圖G 的第k 階譜矩等于G 中長為k 的閉途徑的個數(shù)。

引理2［2］設G 是n 階圖，則

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

引理3［3］設G 是n 階圖，則

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

2 主要結果及其證明

定理1 設G 是n 階簡單圖，H 是G 的一個子圖。若H 能生成長為奇數(shù)的閉途徑，則|E(H) |≥|V( H )|。

證明 由引理4 知，樹子圖只能產(chǎn)生偶數(shù)階的閉途徑。若子圖能產(chǎn)生奇數(shù)階的閉途徑，則它一定含圈。故定理1 成立。

定理2 設G 是n 階簡單圖，則

圖1 圍長為3 邊數(shù)分別為3、4、5 的單圈圖

圖2 圍長為5 或7 邊數(shù)分別為5、6、7 的單圈圖和A6 (3，4)

證明 長為7 的閉回路只可能存在于圖1、圖2 的9 類子圖當中，故只需要考察這9 類子圖中長為7 的閉回路的個數(shù)。

將圈C33 個點標記為a、b、c。從a 點出發(fā)，第一條邊為ab 的閉回路有21 條：ababacba，abababca，ababcaca，ababcaba，ababcbca；abacabca，abacacba，abacbaca，abacbaba，abacbcba；abcababa，abcabaca，abcabcba，abcacaba，abcacaca，abcacbca；abcbabca，abcabcba，abcbcbca，abcbcaca，abcbcaba；從a 點出發(fā)，第一條邊為ac 的閉回路也有21 條。綜上，從a 點出發(fā)長為7 的閉途徑共有42 條。同上，從b（c）點出發(fā)長為7 的閉途徑分別有42 條，所以一個圈C3能產(chǎn)生長為7 的不同閉途徑共126 條。

圈C5頂點分別記為a、b、c、d、e。從a 點出發(fā)，第一條邊是ab，長為7 的不同閉途有ababcdea，abcbcdea，abcdcdea，abcdedea，abcdeaea，abcdeaba。類似地，從a 點出發(fā)，第一條邊是ae，長為7 的不同閉途徑有6 條。根據(jù)對稱性，一個圈C5產(chǎn)生長為7 的不同閉途徑徑共有60 條。

將A6（3，4）中四邊形的4 個點分別記為a、b、c、d，三角形與a 點相連，剩下兩點是e、f。從a點出發(fā)長為7 的不同閉途徑有abcdafea，abcdaefa，adcbafea，adcbaefa，aefabcda，aefadcba，afeabcda，afeadcba；從b 點出發(fā)長為7 的不同閉途徑有baefadcb，bafeadcb，bcdaefab，bcdafeab。類似地，分別從c、d、e、f 出發(fā)長為7 的不同閉途徑也有4 條。因此一個雙圈圖A6（3，4）能產(chǎn)生長為7的不同閉途徑共有28 條。

易知一個圈C7能產(chǎn)生長為7 的不同閉途徑共有14 條。

根據(jù)引理1，定理2 成立。

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

［2］ Cvetkovíc D，Rowlinson P. Spectra of unicyclic graphs［J］.Graph and Combinatorics，1987，3（1）：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 moments of trees with given maximum degree［J］. Applied Mathematics Letters，2011，24（7）：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（5）：927－934.

［7］ 吳亞平，呂康南，付捷. 樹的譜矩研究［J］. 江漢大學學報：自然科學版，2012，40（6）：1－4.