DEPENDENCE POLYNOMIALS

Let the dependence polynomial of a graph G be 1-c1z+c2z2-c3z3+. .. where ck is the number of k-complete subgraphs of G. The dependence polynomial arises in the problem of counting words formed from an alphabet on which some commutativity conditions are placed. The key result is that the reciprocal of the dependence polynomial is the generating function for this problem. We compute dependence polynomials for several classes of graphs and explore their behavior under graph operations. We show the smallest (in absolute value) root of the dependence polynomial is real and positive. This gives a new lower bound on the number of triangles in a K4-free graph: c3≥ 9c2c1-2c31-2(c2 1-3c2) 3 2 27, improving a previous bound of Bollobás. © 1990.