Log-concavity of independence polynomials of the very well-covered graphs generated from the complete bipartite graphs Kt,n
| Autor: | Yi-Xuan Guo, 郭易軒 |
|---|---|
| Rok vydání: | 2011 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 99 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|