Log-concavity of independence polynomials of some kinds of trees

摘要

An independent set in a graph G is a set of pairwise non-adjacent vertices. Let ik(G) denote the number of independent sets of cardinality k in G. Then, its generating functionI(G;x)=∑k=0α(G)ik(G)xkis called the independence polynomial of G (Gutman and Harary, 1983).Alavi et al. (1987) conjectured that the independence polynomial of any tree or forest is unimodal. This conjecture is still open. In this paper, after obtaining recurrence relations and giving factorizations of independence polynomials for certain classes of trees, we prove the log-concavity of their independence polynomials. Thus, our results confirm the conjecture of Alavi et al. for some special cases.