- 學位論文
非常好覆蓋圖形獨立多項式之單峰性及對數凹性與一些互相連結網路之拓撲性質
Unimodality and Log-concavity of Independence Polynomials of Very Well-covered Graphs and Topological Properties of Some Interconnection Networks
摘要
這篇論文分成兩個主要部份, 在第一部份中, 我們討論了“非常好覆蓋圖形獨立多項式的 單峰性和對數凹性”。我們證明了對於任意一個G*圖,當其骨架圖G的穩定性數α(G)不大於8時, 圖形G*的獨立多項式I(G*;x)具有單峰性。另外, 我們也證明了圖形K*2,n的獨立多項式具有 對數凹性及單峰性並擁有唯一的眾數。 在第二部份中, 我們討論了“一些連結網路的拓撲性質”。利用Li 和Peng 兩位學者所 介紹的共軛立方體(DC'n) 圖形之結構, 我們介紹了一個新的連結網路, 稱之為共軛立方延 伸網路(DCEN)。我們也進一步地探討了DCEN 的一些拓撲性質。精確地來說, 我們證 明了DCEN(G)保有了一些原來G圖的好性質, 如漢米爾頓連通性、全域三連通性, 以及通 過每邊的泛圈性, 我們也討論了DCEN(G)的容錯漢米爾頓性質。另外, 論文中也探究循環 圖G(n,4)的4-容錯漢米爾頓連通性以及交代群圖AGn的相互獨立漢米爾頓迴圈的存在性。
並列摘要
There are two main parts in this dissertation. In the first part, we study “Unimodality and log-concavity of independence polynomials of very well-covered graphs”. We show that the independence polynomial I(G*;x) of G* is unimodal for any graph G* whose skeleton G has the stability number α(G)<=8. In addition, we show that the independence polynomial of K*2,n is log-concave with a unique mode. In the second part, we investigate “Topological properties of some interconnection networks”. Using the structures of dual-cubes introduced by Li and Peng, we introduce a new interconnection work, called dual-cube extensive networks (DCEN). Furthermore, we study some topological properties of DCEN. More precisely, we show that DCEN(G) preserves some nice properties of G such as the hamiltonian connectivity, globally 3*-connectivity, and edge-pancyclicity, and also discuss the fault-tolerant hamiltonian property of DCEN(G). In addition, we investigate the 4-fault-tolerant hamiltonicity of circular graphs G(n,4) and the existence of mutually independent hamiltonian cycles of alternating group graphs AGn.