由完全的二部圖Kt,n所生成之非常好覆蓋圖形的獨立多項式之對數凹性

Log-concavity of independence polynomials of the very well-covered graphs generated from the complete bipartite graphs Kt,n

郭易軒(Yi-Xuan Guo)

指導教授 ： 高欣欣

中原大學/理學院/應用數學研究所/碩士(2011年)

https://doi.org/10.6840/CYCU.2011.00226

摘要

一個好覆蓋(well-covered)的圖形是指它所有的最大的獨立集(maximal stable/independent sets)都擁有相同的點數。給定一圖G裡面，令點數為k的獨立集的可能性為sk，且它極大的獨立集(maximum stable sets)的點數稱之為α(G)。如果一個好覆蓋的圖形沒有孤立點並且點數為2α(G)，這種圖形稱做非常好覆蓋的(very well-covered)。圖形的獨立多項式(independence polynomial)被定義為
I(G; x) = Σα(G)k=0 skxk；若對所有的1 ≤ k ≤ α(G)−1， I(G; x)滿足s2k ≥ sk+1sk¡1，這樣I(G; x)就稱為有對數凹性的(log-concave)。給定一個任意圖G，在這圖G每個點都長出一條邊和點，這種圖形就稱作是G¤。很明顯的G¤是個非常好覆蓋的圖形。
在2004年，Levit 和 Mandrescu[17]證明了K¤1,n的獨立多項式有對數凹性。
在2010年，Chen和Wang[8]證明出K¤2,n的獨立多項式也有相同的結果。
本篇論文中，我們把K¤t,n, t ≤ n的獨立多項式寫出來，並且證明當t=3, 4, 5的時候，它們的獨立多項式都擁有對數凹性的性質。

關鍵字

對數凹性 ； 獨立多項式 ； 非常好覆蓋的 ； 好覆蓋的 ； 獨立集

並列摘要

A well-covered graph is a graph in which all maximal stable/independent sets have the same cardinality. Let sk denote the number of stable sets of cardinality k in graph G, and α(G) be the size of a maximum stable set. A well-covered graph G with no isolated vertices is called very well-covered if |G| = 2α(G). The independence polynomial of G is defined by I(G; x) = Σα(G)
k=0 skxk, and I(G; x) is log-concave if s2k ≥ sk+1sk¡1 holds for 1 ≤ k ≤ α(G)−1.
Given an arbitrary graph G, G¤ is the graph obtained from G by appending a single pendant edge to each vertex of G. It is easy to see that G¤ is very well-covered.
In 2004, Levit and Mandrescu [17] proved that the independence polynomial of K¤1,n is log-concave. In 2010, the same result for K¤2,n is proved by Chen and Wang [8]. In this thesis, we find the independence polynomials I(K¤t,n; x) of K¤t,n for all positive integers t ≤ n and show that I(K¤t,n; x) is log-concave for any t with 3 ≤ t ≤ 5.

並列關鍵字

well-covered ； very well-covered ； log-concave ； stable/independent set ； independence polynomial

參考文獻

[6] J.I. Brown, R.J. Nowakowski, and I.E. Zverovich, The structure ofwell-covered graphs

York, 1980.

[3] J.I. Brown, K. Dilcher, and R.J. Nowakowski, Roots of independence polynomials of

well-covered graphs, J. Algebr. Comb. 11 (2000), 197–210.

[4] J.I. Brown and R. Hoshino, Well-covered circulant graphs, Discrete Math. 311 (2011),