摘要 一個(gè)圖是譜確定的，簡單地說是指，任何與它不同構(gòu)的圖必定和它具 有不同的譜目前對(duì)譜確定問題的研究結(jié)果( 包括尋找同譜對(duì)) 并不多， 半個(gè)世界以來，出現(xiàn)了一些用鄰接譜和l a p l a c i a n 譜來刻畫一些特殊結(jié)構(gòu) 圖的文章，以及少量用特征值和角共同刻畫一些特殊圖的文章在前人的 基礎(chǔ)上，本文通過計(jì)算圖的鄰接特征多項(xiàng)式，閉路數(shù)目，利用二部圖同 l a p l a c i a n 譜必l i n e 一同譜的性質(zhì)，以及有相同特征值和角的圖的一些特 點(diǎn)來研究一些特殊結(jié)構(gòu)的非正則圖的譜( 和角) 確定問題，得到了如下一 些結(jié)論： ( 1 ) 兩個(gè)不同構(gòu)的c 。，n 。陽，m 圖沒有相同的鄰接譜 ( 2 ) 圖s 1 , 1 , 1 , 2 1 + 1 不能由鄰接譜確定，其中2 1 ( 3 ) 兩個(gè)不同構(gòu)的圖q ， 沒有相同的鄰接譜 ( 4 ) 冠圖go 虬可由其l a p l a c i a n 譜確定，其中n 為偶數(shù) ( 5 ) 圖舢可由其l a p l a c i a n 譜確定，其中m 為偶數(shù) ( 6 ) 冠圖go 研可由其特征值和角確定 ( 7 ) 圖，p ，?？捎善涮卣髦岛徒谴_定，其中m 為奇數(shù) ( 8 ) 單輪圖+ ?？捎善涮卣髦岛徒谴_定 ( 9 ) 樹l 可由其特征值和角確定 ( 1 0 ) 圖，即可由其特征值和角確定，其中m 為奇數(shù) ( 1 1 ) 冠圖r ok t ，飽和烷烴分子g 也。+ z 的分子圖可由其特征值和角 確定 關(guān)鍵詞：鄰接矩陣，l a p l a c i a n 矩陣，特征值，鄰接譜，l a p l a c i a n 譜，同譜圖，角， 頂點(diǎn)度對(duì)，冠圖 i i a b s t r a c t ag r a p hi ss a i dt ob ed e t e r m i n e db yi t ss p e c t r u mi ft h e r ei sn oo t h e rn o n - i s o m o r p h i cg r a p hw i t ht h es a n l es p e c t r u m a n s w e r i n gt h i sp r o b l e ms e e m so u to f r e s e a r c h ( i n c l u d i n gf i n d i n gc o s p e c t r a lg r a p h s ) ，n o w a tt h eb a s i so ft h e m ，i nt h i s p a p e r ，b yc a l c u l a t i n ga d j a c e n c yc h a r a c t e r i s t i cp o l y n o m i a l ，t h en u m b e ro fd o s e d - c i r c u i t ，u s i n gt h ep r o p e r t yt h a tb i p a r t i t eg r a p h sw i t hs a m el a p l a c i a ns p e c t r u m m u s tb el i n e - c o s p e c t r a la n dt h ep r o p e r t yo fg r a p h sw i t ht h es a m ee i g e n v a l u e sa n d a n g l e st os t u d ys o m en o n r e g u l a rg r a p h sw i t hs p e c i a ls t r u c t u r e w ep r o v et h a t ： ( 1 ) n og r a p h sg l m ，n 3 ，批8 , r ec o s p e c t r a l ( 2 ) g r a p h ss 1 ，1 ，1 ，雹+ l 謝t h 之n o te q u a l1i s n td e t e r m i n e db yi t sa d j a c e n c ys p e c - t r u m ( 3 ) n og r a p h sq g ，sa r ec o s p e c t r a l ( 4 ) t h ec o r o n ao fqa n d 廄w i t hne v e ni sd e t e r m i n e db yt h e i rl a p l a c i a n s p e c t r u m ( 5 ) g r a p hz k p l 口w i t hme v e ni sd e t e r m i n e db yi t sl a p l a c i a ns p e c t r u m ( 6 ) t h ec o r o n ao fq a n dk 1i sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 7 ) g r a p h p ，g w i t hm o d di sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 8 ) s i n g l ew h e e lg r a p h + 1i sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 9 ) t h et r e e 死i sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 1 0 ) g r a p hc k sw i t hpo d di sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 1 1 ) t h ec o r o n ao fr a n dka n dak i n do fm o l e c u l a rg r a p ho fa n ( y la r ec h a r - a c t e r i z e db ye i g e n v a l u e sa n da n g e l s i i i k e y w o r d s ：a d j a c e n c ym a t r i x ，l a p l a c i a nm a t r i x ，e i g e n v a l u e s ，a d j a c e n c ys p e c t r u m ， l a p l a c i a ns p e c t r u m ，c o s p e c t r a l ，a n g e l ，v e r t e xd e g r e ep a i r ，c o r o n a i v 湖南師范大學(xué)學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn) 行研究所取得的研究成果除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文 不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品對(duì)本文的研究 做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明本人完全意識(shí) 到本聲明的法律后果由本人承擔(dān) 學(xué)位論文作者簽名：參f 翼肇勁1 年6 月7 日 湖南師范大學(xué)學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了餌學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，研究 生在校攻讀學(xué)位期間論文工作的知識(shí)產(chǎn)權(quán)屬湖南師范大學(xué)，同意學(xué)校保 留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查 閱和借閱本人授權(quán)湖南師范大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編 人有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯 編本學(xué)位論文 本學(xué)位論文屬于 1 、保密口，在 年解密后適用本授權(quán)書 2 、不保密甌 ( 請(qǐng)?jiān)谝陨舷鄳?yīng)方框內(nèi)打“、 ) 日期：研年6 月7 日 醐叩石月尸日 苓一翠jf 蓼壤 j d劉v萇 名 名 簽 簽 者 師 作 導(dǎo) 由圖的譜( 和角) 確定的問題 1 緒論 1 1 譜確定及相關(guān)問題的研究背景 圖的譜確定問題是圖論中的一個(gè)重要問題，主要涉及圖的鄰接譜與圖 的l a p l a c i a n 譜的研究，其研究的主要途徑是通過圖的矩陣( 鄰接矩陣或 l a p l a c i a n 矩陣) 表示，建立圖的拓?fù)浣Y(jié)構(gòu)( 特別是圖的各種不變量) 和圖的 矩陣表示的置換相似不變量之間的聯(lián)系，通過矩陣論，以及組合矩陣論中 的經(jīng)典結(jié)論，用于圖的拓?fù)浣Y(jié)構(gòu)的研究 1 9 5 6 年，g f i n t h a r d 和階i m 口s 在一篇把圖譜理論與化學(xué)中h f i c k e l 7 s 理論 相聯(lián)系的論文 7 1 中提出了“哪些圖由它們的譜確定? 升這一問題，那時(shí)人。 們認(rèn)為所有的圖都能由它的譜確定，但是，一年以后，c o l l a t z 和s i n o g o w i t z 找到了一對(duì)同譜圖1 9 6 6 年，f i s h e r 1 1 】在考慮k a c 1 7 1 提出的問題：“一個(gè)人 能否聽到鼓聲的形狀? ”時(shí)用一個(gè)圖模擬了鼓聲的形狀，這樣，鼓聲就可以 用圖的特征值刻畫 所謂圖的“譜確定問題”，簡單地說是指，根據(jù)已有的特征值是否可以 確定出唯一的圖，如果存在兩個(gè)或者更多的圖具有一樣的譜，那么這些圖 便是同譜圖所以，尋找同譜圖也是譜確定問題的范疇自1 9 6 7 年后，許 多同譜圖的例子已經(jīng)找到，其中令人驚奇的結(jié)論是：s c h w e n k 2 6 在1 9 7 3 年 聲明幾乎所有的樹都不能由它們的鄰接譜確定后來，g o d s i l 和m c k a y 證 明了幾乎所有樹的補(bǔ)圖都不能由它們的鄰接譜確定m c k a y 還證明了幾乎 所有的樹都不能由它們的l a p l a c i a n 譜確定【2 3 】在這些結(jié)論后，關(guān)于一般 的圖是否由它們的譜確定的問題就沒有統(tǒng)一的結(jié)論幾乎所有的圖都由 它的譜確定? 還是幾乎所有的圖都不能由它們的譜確定? 或者二者都不 是? 迄今為止，我們知道扎個(gè)頂點(diǎn)的已知的非譜確定圖的比例遠(yuǎn)遠(yuǎn)大于已 知的譜確定圖的比例，但當(dāng)禮葉o o 時(shí)這兩個(gè)比例都趨于零計(jì)算機(jī)的計(jì) 碩士學(xué)位論文 算結(jié)果表明大部分1 1 個(gè)頂點(diǎn)( 或更少的頂點(diǎn)) 的圖是譜確定圖，但是，當(dāng)n 逐漸變大時(shí)，計(jì)算機(jī)很難運(yùn)算出結(jié)論 對(duì)于那些不能譜確定的圖形，為了更好地刻畫它的特征，還引入了一 個(gè)新的變量一角，這在 s l 中有較多的介組 1 2 概念與記號(hào) 本論文只研究簡單無向圖，設(shè)g = ( y ( g ) ，e ( g ) ) 是一個(gè)簡單無向圖，其 點(diǎn)集和邊集分別是v ( a ) 和e ( g ) ，對(duì)任意的 v 點(diǎn) 的度表示為也，圖 g 的頂點(diǎn)度序列記為d 。d 2 d n ，記最大度= d l ，最小度6 = 如 ，r 圖g 的鄰接矩陣定義為a ( g ) ：( 口幻) ，這里o ；j ： 二 ? “? ，矩陣 l u o 和3 l ( g ) = d ( g ) 一a ( g ) 稱為圖g 的l a p l a c i a n 矩陣，其中d ( g ) 是n x 他的頂點(diǎn) 度對(duì)角矩降多項(xiàng)式r ( g ) ( a ) = d e t ( m a ( g ) ) ( 或兄( g ) ( 肛) = d e t ( m l ( g ) ) ， 定義為g 的鄰接特征多項(xiàng)式( 或l a p l a c i a n 特征多項(xiàng)式) ，其中，是單位矩 陣，設(shè)入1 入2 a n ，p 1 p 2 腳( = 0 ) 分別是圖g 的鄰接特征 值，l a p l a c i a n 特征值圖g 的鄰接譜( 或l a p l a c i a n 譜) 分別由圖g 的鄰接 特征值( 或l a p l a c i a n 特征值) 組成 具有相同的鄰接譜( 或l a p l a c i a n 譜) 的圖稱為鄰接同譜圖( 或l a p l a c i a n 同譜圖) ，若圖h 和g 具有相同的鄰接譜( 或l a p l a c i a n 譜) ，并且日和g 不同構(gòu)，則圖日稱為圖g 的鄰接同譜對(duì)( 或l a p l a c i a n 同譜對(duì)) 圖1 - 1 和圖 1 - 2 分別給出了一對(duì)鄰接同譜圖和一對(duì)l a p l a c i a n 同譜圖 a 1 1 如果兩個(gè)圖 的線圖關(guān)于鄰接矩陣同譜，那么這兩個(gè)圖稱為l i n e - 同譜；如果樹t 中某 個(gè)頂點(diǎn) 的度大于或等于3 ，則稱口為大頂點(diǎn) 給定兩個(gè)圖g 。和g ：，圖g 稱為g t 和g 。的不相交的并( 或和) ，記為 g = g 1 + g 2 ，若v ( a ) = y ( a 1 ) uv ( a 2 ) 和e ( c ) = e ( g i ) ue ( g 2 ) 2 由圖的譜( 和角) 確定的問題 圖1 - 1 鄰接同譜對(duì)圖1 - 2l a p l a c i a n 同譜對(duì) 下面給出角的定義：設(shè)u 1 u 2 是a 的特征值入l 入2 入n 中的所有不同值，并設(shè) e 。，e 2 ，e n ) 為彤的一組標(biāo)準(zhǔn)正交基，鄰接矩 陣a 有譜分解a = v l r + 忱b + + p m ，只指從艫到特征空間e ( v t ) 的正 交映射( 其中砰= 只= p s ；i = 1 ，m ；只弓= 0 ，i j ) o t i i = c d s 如( 其中島 是e ( v i ) 與e 1 之間的角，a o 0 ) 稱為g 的角，且q 巧= l i p i e j l l ，o i l ，o t i 2 ，q i n 是第i 個(gè)特征值角序列，q u ，o t 2 j ，q 叮是第j 個(gè)頂點(diǎn)角序列，a 的角矩陣 定義如下：a = 0 q 巧l l m 。，角矩陣是一個(gè)圖變量如果一個(gè)圖不變量( 或參 數(shù)) 能由特征值和角確定，則稱此不變量或參數(shù)是e a 一可重構(gòu)的接下來 給出頂點(diǎn)度對(duì)的定義：若移是圖g 的一個(gè)頂點(diǎn)，d t 是頂點(diǎn)口的度，e 是頂 點(diǎn)u 的所有鄰域的度之和，則稱( 也，e ) 為頂點(diǎn)口的度對(duì)對(duì)于角的更多性 質(zhì)可參考【5 】 1 3譜確定及相關(guān)問題的研究現(xiàn)狀 下面列舉出譜確定問題中一些由鄰接譜，l a p l a c i a n 譜或者由特征值和 角共同確定的已有結(jié)果 1 k 個(gè)不相交的完全圖的并，+ ：+ + 。由它的鄰接譜確定i s l 2 k 個(gè)不相交的路圖的并p m 。+ p m 2 + + p m 。，k 個(gè)不相交的圈g ，+ g ：+ + g 。的并既能由它們的鄰接譜確定，又能由它們的l a p l a c i a n 譜確 定【3 l i 。其中m 2 ，t i 3 ( i = 1 ，2 ，k ) 3 k 個(gè)不相交的階為l 的完全圖的并k k t ，線圖l ( k n ) ( n 8 ) 和線圖 3 碩士學(xué)位論文 l ( ，。) ( m 4 ) 及它們的補(bǔ)圖，階為( 3 ，6 ) 的廣義四邊形的點(diǎn)圖等既能由 它們的鄰接譜確定，又能由它們的l a p l a c i a n 譜確定【3 4 正則圖中，t 個(gè)完全相同的強(qiáng)正則譜確定圖的不相交的并，c 5 以， i o ( m ，m 一1 ，m 一2 ) 以，既能由它們的鄰接譜確定，又能由它們的l a p l a c i a n 譜確定【3 1 1 5 l o l l i p o p 既由它們的鄰接譜確定，又由它們的l a p l a c i a n 譜確定 1 4 1 ，【3 】 6 若二部圖g 有三個(gè)不同的特征值a 。，a ：，a 。，重?cái)?shù)分別為m 。，m 2 ，m 。， 則a 3 = 一a ，a 2 = 0 ，m 3 = r r t l ，g 是m - 個(gè)完全二部圖紙 的直和，且有 t t 2 一詈( n + s t 一2 ) 個(gè)孤立點(diǎn)，這里 i s 產(chǎn)增，i = 1 ，2 ，m 1 進(jìn)一步，若圖 g 是上述圖且礙= p , p 是素整數(shù)，則g 由它的鄰接譜確定i s ) 7 具有三個(gè)鄰接特征值且最小特征值為一2 的非正則圖中有5 個(gè)能由 鄰接譜確定【3 2 j 8 正則完全多部圖既能由它們的鄰接譜確定，又能由它們的l a p l a c i a n 譜確定【1 0 j 【1 9 1 9 路的補(bǔ)圖由鄰接譜確定1 9 1 1 0 圖磊由它們的鄰接譜確定，圖磊的k 個(gè)不相交的并 ，+ z m 2 + + 。由它們的鄰接譜確定，其中m ；2 ( i = 1 ，2 ，七) 矧 1 1 沒有兩棵不同構(gòu)的似星型樹同譜( 2 0 1 1 2 t 型樹t ( 1 l ，1 2 ，f 3 ) 能由它的鄰接譜確定，其中( 1 1 ，2 2 ，f 3 ) ( i ，1 ，2 1 2 ) ， 且l 2 為整數(shù)【3 3 】 1 3 所有最大特征值不大于、2 + 鋸的連通圖由其鄰接譜確定【捌 1 4 設(shè)g = 乙，+ 歷。+ + + t 1 丑+ 2 乃+ 如忍的鄰接譜半徑a l 2 ，那 么g 由它們的鄰接譜確定當(dāng)且僅當(dāng)g 中不含這樣的部分：它們的不相交 4 由圖的譜( 和角) 確定的問題 的并的譜等于反( i = 1 ，4 ) t 2 4 l 1 5 h a m m i n g 圖h ( 3 ，g ) ( g 3 6 ) 由鄰接譜確定【l 】 1 6 圖，瓦，七磊由它們的l a p l a c i a n 譜確定m 1 7 設(shè)g = z j l + z j 2 + + 蘇+ t i t l + t 2 t 2 + t 3 t 3 的鄰接譜半徑a l p 1 ( g ( 七+ 1 ，z 一1 ) ) 引理2 7 1 7 1 增大非負(fù)矩陣a 的任一元素，a 的最大特征值不會(huì)減小j 如 果a 是不可約矩陣，則增大a 的元素，a 的最大特征值會(huì)嚴(yán)格增大 引理2 8 1 1 9 1p ，設(shè)圖g 有n 個(gè)頂點(diǎn)和m 條邊，令d = ( d 1 ，d 2 ，厶) 是它 的不增度序列，則兄( g ) ( p ) 中的一些系數(shù)為 q o = 1 ；q l = 一2 m ；q 2 = 2 m 2 一m 一互1 竺1d i 2 ； q 3 = ( 一4 m 3 + 6 m 2 + 3 m ：1 霹一ld 3 3 ：1 霹+ t r ( a 3 ) ) ， 一1 = - 1 艫1 禮s ( g ) ；q n = 0 俐從圖g 的l a p l a c i a n 譜，可以得到： 俐圖g 的連通分支數(shù)j 俐圖g 的生成樹的數(shù)目 弓l 理2 9 1 1 9 1 ，【2 1 】設(shè)圖g 中，v ( a ) d ，e ( g ) d ，見l | ( g ) + 1 p l a 。( s ) ，此時(shí)日與s 不 同譜，矛盾! 當(dāng)有兩個(gè)最大度a ( h ) = 3 時(shí)，日可能的圖為脅，風(fēng)，但是a ，( h 7 ) = 2 0 5 2 8 8 a l ( s ) ，a l ( 風(fēng)) = 2 口2 ，此時(shí)右邊最高項(xiàng)為一2 t 學(xué)，所以p 1 = p 2 ，9 1 = q 2 ( 3 - 6 ) ( 3 - 7 ) 由圖的譜( 和角) 確定的問題 此時(shí)g 。與g 2 同構(gòu) ( 2 ) 當(dāng)p 1 ：9 1 時(shí)，( 3 7 ) 式左邊最高項(xiàng)為一4 t 學(xué) 若船 9 2 ，則右邊最高項(xiàng)為一2 t 掣，矛盾! 所以p 2 = ( 2 ，得到p 1 = p 2 ，q l = q 2 此時(shí)g 。與g z 同構(gòu) 情形2 ：當(dāng)5 2 時(shí)，先計(jì)算q 島。的特征多項(xiàng)式，( 下將其簡記為g ) ，反 復(fù)利用引理2 2 ，并記p + 口+ s = n 得： ( g ，a ) = ( q ) 驢( 日q + 。，g ) 一妒( 弓一) 妒( + 8 - 1 ，口) 再利用引理2 3 及【1 2 】的結(jié)果整理后代入得： ( g ；t + t i 1 ) ( 1 一t 2 )( 暑+ t 一暑一2 ) 【t 一半( 1 2 t + t q 一2 t + 2 t 警) + t 字( t 2 2 t + 2 t j 產(chǎn)+ t q + 2 2 t _ 皆) ) 一摯- i 一學(xué)( 1 2 t + t q 一2 t 墨+ 2 亡z 筍) + t 半( t 2 2 t + 2 t 鼉筍+ 一q + 2 2 t 鼉筍) ) ( t 暑+ t 一羞一2 ) t 一- 峙- t 2 + ( i 一2 t + t q 一2 t s 2 + 2 t 孚) + ( t 墨+ 一呈一2 ) t 字( t 2 2 t + 2 t j 乒+ t - q + 2 2 t j 乒) 一二堅(jiān)軍塵( 1 2 t + t q 一2 t 墨+ 2 t 字) 一三二蘭掣( 2 2 t + 2 z j 蘆+ 一q + 2 2 舌鼉蘆) = ( 1 2 t + t q 一2 t 蘭+ 2 t 警) ( 衛(wèi)習(xí)= 三+ t 一號(hào)一2 t 一半 一t p + 蘭+ 萼 ) + ( t 2 2 t + 2 t 二乒+ t 一口+ 2 2 t 二：拳) ( t 鼉 + t 半一2 t 啦2 一魚t - 1 + 嚳) 碩士學(xué)位論文 于是，咖( g ；t + t 一 ) ( 1 一t 2 ) ( t 1 ) = ( 1 2 t + t q 一2 墨+ 2 半) ( t 甲+ 一號(hào)一2 t j 產(chǎn)) ( t 一1 ) 一礦1 一號(hào)+ t 1 一號(hào)) + ( t 2 2 t + 2 j 乒+ t q + 2 2 t j 乒) ( t 詈+ t 1 氣= 2 2 t 字) ( t 一1 ) 一號(hào)+ t 半) = ( 1 2 t ) ( 2 t 1 一號(hào)一z 一號(hào)) + ( t 2 2 t ) ( t 暑+ 1 2 號(hào)) + ( 1 2 t ) ( 一2 生產(chǎn)一羋 + 2 亡鼉產(chǎn)) + ( t 。一2 墨+ 2 t 墨+ 1 ) ( 2 t 1 一號(hào)一t 一號(hào)) + ( t q 一2 t 墨+ 2 t 墨+ 1 ) ( 一2 t 呈= 產(chǎn)一 t 半+ 2 t 二5 產(chǎn)) + ( t 2 2 t ) ( 亡華+ 1 2 t 字+ 1 + 2 t 字) + ( 2 t 一墨+ 1 + t 一口+ 2 2 t 一墨+ 2 ) ( t 詈+ 1 2 z 號(hào)) + ( 2 t 一墨+ 1 + t 一口十2 2 t 一墨+ 2 ) ( t 午+ 1 2 t 字+ 1 + 2 t 字) = ( 1 2 t ) ( 2 t 1 一號(hào)一t 一號(hào)) + ( t 2 2 ) ( t 號(hào)+ 1 2 t 號(hào)) + 4 t 3 + 暑一1 2 t 2 + 考十1 2 t 1 + 暑一4 t 量 一t 罟一t 一6 警+ 1 一字+ 2 z 孚+ 6 孚+ 2 + 2 衛(wèi)鼉衛(wèi)+ 1 + 2 t q + 1 一號(hào)一t q 一號(hào) + 2 z 墨一號(hào)+ 4 t + 2 一號(hào)一6 旦專苧+ 1 + 2 字+ 2 警一2 1 + 孚+ t 牛棚一2 t 字+ 3 + 6 亡字+ 2 2 午+ 2 + 6 亡詈一墨+ 2 4 t 詈一+ l 一6 t + 1 一詈+ t 詈一q + 3 2 t 詈一q + 2 2 亡號(hào)一；+ 3 + 2 亡2 + 竽+ 亡甲+ 3 4 3 + 孚 ( 孓8 ) 設(shè)g 1 = q 。舭。與g 2 = 艦。同譜，且p 1 9 1 ，p 2 q 2 ， 由( g 1 ；t 百1 + 一互1 ) = 咖( g 2 ； + t 一) 得， ( g 1 ； + t 一 ) ( 1 一2 ) ( 亡一1 ) = 砂( g 2 ；+ z 一 ) ( 1 一t 2 ) ( 亡一1 ) 分別以p - ，q 1 與p 。，q 2 代入( 3 8 ) 的右端，則相應(yīng)的右端相等，分別記作 。與妒2 ， 去掉。與砂7 ：中的公共部分后，等式兩端仍記為妒7 。= 7 ： ( 1 ) 當(dāng)q 1 = p 1 時(shí)，經(jīng)比較l 中的最高項(xiàng)為一4 t 罟一等+ 3 若q 2 p 2 ，則2 中的最高項(xiàng)為一2 謦+ 號(hào)+ 3 ，矛盾! t 口n 于是q 2 = p 2 ，義p 1 + 9 1 + s = p 2 + 9 2 + s ， 所以p l = p 2 ，9 1 = q 2 2 0 由圖的譜( 和角) 確定的問題 此時(shí)g ，與g 2 同構(gòu) ( 2 ) 當(dāng)q l p 1 時(shí)，經(jīng)比較l 中的最高項(xiàng)為一2 t 謦+ 暑+ 3 若q 2 = p 。，則2 中的最高項(xiàng)為一4 攜一警 ，矛盾! 所以q 2 p 2 ，此時(shí)2 中的最高項(xiàng)為一2 警+ 差+ 3 可得p t = p 2 ，9 1 = q 2 ， 于是g 。與g z 同構(gòu) 3 4 冠圖go ( 1 由l a p l a c i a n 譜確定，其中n 為偶數(shù) 先給出冠圖n c ok 1 的定義：它由圈圖q 上的每一個(gè)頂點(diǎn)分別與 個(gè)只相連而得到，亦如下圖所示： 圖3 - 7 定理3 4 冠圖ok l 由l a p l a c i a n 譜確定，其中n 為偶數(shù) 證明：假設(shè)圖g 與go 關(guān)于l a p l a c i a n 矩陣同譜，那么g 有加個(gè)頂點(diǎn)， 由引理2 8 知，圖g 與go 甄有相同的l a p l a c i a n 特征多項(xiàng)式，相同的邊數(shù) 和生成樹數(shù)目以及連通分支數(shù)目， 因?yàn)間o 甄連通分支數(shù)為1 ，邊數(shù)為2 船，所以g 為連通的單圈圖， 又g ok 1 的生成樹數(shù)目為n ，于是g 的生成數(shù)數(shù)目為佗，所以g 所含 2 1 碩士學(xué)位論文 圈的圈長為m 運(yùn)用引理2 8 知：銎。霹= 鍪。云2 ，其中d i ，玉分別是圖g 與圖go 虬 中的頂點(diǎn)仇的度， 運(yùn)用引理2 9 知，4 u l ( c ok 1 ) 5 ， 那么g 的最大度小于等于4 ，假設(shè)g 中存在z 個(gè)頂點(diǎn)度為1 的點(diǎn)，y 個(gè) 頂點(diǎn)度為2 的點(diǎn)，z 個(gè)頂點(diǎn)度為3 的點(diǎn)，w 個(gè)頂點(diǎn)度為4 的點(diǎn)，則 i z + 2 + 3 z + 4 w = 4 n ( 3 - 9 ) z 十y + z + w = 2 n ( 3 - 1 0 ) iz + 4 y + 9 z + 1 6 w = 1 0 n ( 3 - 1 1 ) 當(dāng)n 為偶數(shù)時(shí)，g 與go 致均為二部圖，由它們的l a p l a c i a n 矩陣同譜 以及引理2 1 0 知，g 的線圖l i n e ( g ) 與qo 甄的線圖l i n e ( c o1 ( 1 ) 的鄰接 矩陣同譜所以，l i n e ( g ) 與l i n e ( c o ) 中所含三角形個(gè)數(shù)相等于是， 幾( 三) = z ( 蘭) + 叫( 三) 得到1 , = z + 4 w( 3 - 1 2 ) f z = m 由( 3 - 0 ) ，( 3 - 1 0 ) ，( 3 - 1 1 ) ，( 3 - 1 2 ) 得 可_ 0 忙鼉 因此g 與go 所同構(gòu)證畢 對(duì)一個(gè)圖而言，它的l a p l a c i a n 特征值決定了它的補(bǔ)圖的特征值。于 是得到下面的推論 推論3 4 冠圖q ok ，的補(bǔ)圖由l a p l a c i a n 譜確定，其中幾為偶數(shù)。 3 5 圖，舢由l a p l a c i a n 譜確定，其中m 為偶數(shù) 2 2 由圖的譜( 和角) 確定的問題 首先給出圖藏g 的定義：它指由圈圖上的一個(gè)頂點(diǎn) 與兩條頂 點(diǎn)數(shù)分別為p ，q 的路弓以及島的一個(gè)懸掛點(diǎn)分別相連而得到的圖，亦如 下圖所示： 圖3 _ 8 2 定理3 5 圖日m 舢由l a p l a c i a n 譜確定，其中m 為偶數(shù) 氣 證明：設(shè)n = m + p + q ，假設(shè)圖g 與 p 口關(guān)于l a p l a c i a n 矩陣同譜f 那么g 有n 個(gè)頂點(diǎn)，由引理2 8 知，g 與刪有相同的特征多項(xiàng)式，相 同的邊數(shù)和生成樹數(shù)目以及連通分支數(shù)目。與定理3 4 的證明類似：可證 得g 為連通的單圈圖，且圈長為m ，運(yùn)用引理2 9 得 5 p ，則q 1 q ，由引理2 6 知： a ( g ) = a l ( ，p 。，口1 ) 入1 ( ，m ) ，矛盾! 因此p 1 = p ，q 1 = q ， 此時(shí)g 和如，加同構(gòu) 口 ( 3 - 1 6 ) 由圖的譜( 和角) 確定的問題 4 幾類特殊圖的特征值和角確定問題 4 1 冠圖go ( 1 由特征值和角確定 定理4 1 冠圖go 甄由特征值和角確定 證明：假設(shè)圖g 和q 。有相同的特征值和角q 巧， ( i = 1 ，m ；j = 1 ，2 n ) ， 則由引理2 1 3 ，2 1 4 知圖的連通與否是e a 一可重構(gòu)的，是否為單圈圖 亦是e a 一可重構(gòu)的， 因?yàn)間 ok 。是連通的單圈圖，所以g 也是連通的單圈圖設(shè)g 所含 圈的圈長為8 ，下面就禮的奇偶性分兩種情形討論： 情形1 ：當(dāng)n 為奇數(shù)時(shí)，圖g ok a 非二部圖 若s 為偶數(shù)，則g 為二部圖，矛盾! 所以s 為奇數(shù)。 若n s ，則go 甄中長為s 的閉路數(shù)目為0 ，而g 中長為s 的閉路數(shù) 目為l ，由引理2 4 知，如果兩個(gè)圖的鄰接特征值相同，則它們含有相同的 任意長度的閉路數(shù)目，矛盾! 若n s ，必n s 2 ，則g 必包含圖g ，作為子圖( 見下圖4 1 ) 圖4 - 1 由 2 】知：印e c ( gok x ) = 卜士v 1 一c o s 2 誓+ 1 “c d 舡節(jié)“即，士厴) 所以，a l ( g ok 1 ) = 1 + 以= a 1 ( g o 研) ， 而入1 ( go 所) 3 ， 則x 的頂點(diǎn)度對(duì)為 ( 1 ，4 ) ，( 1 ，4 ) ，( 4 ，7 ) ，( 4 ，7 ) ，( 4 ，1 0 ) ，( 4 ，1 0 ) 】， _ l _ - _ - _ 、j _ _ _ - l _ l ，、_ _ _ l l _ - _ o 、j - _ i _ l _ l i _ ， 2 m + 2m - - 2 設(shè)圖x 與圖x 有相同的特征值和角，則x 7 有m 個(gè)4 度頂點(diǎn)，2 m + 2 個(gè)懸掛頂息如果圖x 中有一個(gè)4 度頂點(diǎn)缸與三個(gè)4 度頂點(diǎn)鄰接，則u 的頂點(diǎn)度對(duì)為( 4 ，n ) ( n 1 3 ) ，矛盾! 所以圖x 的每個(gè)4 度頂點(diǎn)至多與兩個(gè)4 度頂點(diǎn)鄰接，則x 與圖 同構(gòu)證畢 類似地，我們可以證明下面的圖4 - 8 可以由特征值和角確定 圖4 8 證明：用y 表示上面的圖，假設(shè)圖y 與圖y 有相同的特征值和角與 定理4 5 2 證明類似可得，y 是有仇個(gè)3 度頂點(diǎn)，m + 2 個(gè)1 度頂點(diǎn)的樹若 圖y 7 的一個(gè)3 度頂點(diǎn)u 與三個(gè)3 度頂點(diǎn)鄰接，則頂點(diǎn)u 的度對(duì)為( 3 ，9 ) 而 圖y 的頂點(diǎn)度對(duì)序列為【( 1 ，3 ) ，( 1 ，3 ) ，( 3 ，5 ) ，( 3 ，5 ) ，( 3 ，7 ) ，( 3 ，7 ) ) ，故y ， 、- _ - _ 、一一l _ 一、- i i _ - 、一- l _ _ - ， m + 2m 一2 的頂點(diǎn)度對(duì)為 ( 1 ，3 ) ，( 1 ，3 ) ，( 3 ，5 ) ，( 3 ，5 ) ，( 3 ，7 ) ，( 3 ，7 ) ，不存在頂點(diǎn)度對(duì) 、_ _ _ - i 一、一i l - ，、- _ _ _ l - 、一一_ _ _ _ 一 ，n + 2m - 2 為( 3 ，9 ) ，矛盾! 因此圖y 7 的每個(gè)3 度頂點(diǎn)至少與一個(gè)懸掛點(diǎn)鄰接，這就使得y 與y 同構(gòu) 口 由圖的譜( 和角) 確定的問題 結(jié)語 本文通過計(jì)算圖的鄰接特征多項(xiàng)式，閉路數(shù)目，利用二部圖同l a p l a c i a n 譜必l i n e 一同譜的性質(zhì)，以及有相同特征值和角的圖的一些特點(diǎn)來研究 一些特殊結(jié)構(gòu)的非正則圖的譜( 和角) 確定問題，得到了一些結(jié)論其中 冠圖go 研在n 為奇數(shù)時(shí)以及圖，m 在m 為奇數(shù)時(shí)是否由l a p l a c i a n 譜確定；圖，m 和圖 ，在m 為偶數(shù)時(shí)是否由特征值和角確定，仍有 待解決，是本論文的開放性問題，由圖的譜( 和角) 確定的問題值得更深 入的探討 參考文獻(xiàn) 【1 】b a n g ，s e r v a nd a m j h k o o l e n s p e c t r a lc h a r a c t e r i z a t i o no ft h e h a m m i n gg r a p h s j 。l i n e a ra l g e b r aa p p l , 2 0 0 8 ，( 4 2 9 ) ：2 6 7 8 - 2 6 8 6 【2 】b a r i k ，s s p a t i b k s a r m a t h es p e c t r u mo ft h ec o r o n ao ft w o g r a p h s j d i s c r e t em a t h ，2 0 0 7 ，( 2 1 ) ：4 7 - 5 6 【3 】b o u l e t ，r b j o u v e t h el o l l i p o pg r a p hi sd e t e r m i n e db yi t ss p e c t r u m 【j 】- t h ee l e c t r o n i cj o u r n a lo fc o m b i n a t o r i c s ，2 0 0 8 ，( 1 5 ) 【4 】b i g g s ，n a l g e b r a i cg r a p ht h e o r y ，s e c o n de d m c a m b r i d g e ：c a m b r i d g e u n i v e r s i t yp r e s s ，1 9 9 3 【5 】c v e t k o v i d ，d p r o w l i s o n s s i m i d e i g e n s p a c e so yg r a p h s 【m 】c a m - b r i d g e ：c a m b r i d g eu n i v e r s i t yp r e s s ，1 9 9 7 ，1 ：7 5 8 5 【6 】c v e t k o v i 6 ，d p r o w l i s o n s s i m i d s i g n l e a sl a p l a c i a n so ff i n i t e g r a p h s j l i n e a ra l g e b r aa p p f j 2 0 0 7 ，( 4 2 3 ) ：1 5 5 - 1 7 1 【7 】c v e t k o v i 6 ，m m d o o b & h s a c h s s p e c t r a lo