A bound on the values of independence polynomials at for -degenerate graphs

详细信息    查看全文

• 作者：John Estes ; William Staton ; Bing Wei
• 关键词：Fibonacci number of a graph ; Independence polynomials ; kk-trees ; kk-degenerate graphs
• 刊名：Discrete Mathematics
• 出版年：2013
• 出版时间：28 September, 2013
• 年：2013
• 卷：313
• 期：18
• 页码：1793-1798
• 全文大小：386 K

文摘

An independent set of a graph is a set of pairwise non-adjacent vertices. Let denote the cardinality of a maximum independent set and for denote the number of independent sets on vertices. The independence polynomial defined first by Gutman and Harary in 1983 has been the focus of considerable research. In 1995, Wingard bounded the function values obtained at for the independence polynomials for the tree ; . We generalize Wingard¡¯s result for a much larger class of graphs, -degenerate graphs, a class which includes all -trees. Wingard¡¯s result is the case when .