A Generalization of Clique Polynomials and Graph Homomorphism

The clique polynomial of a graph G is the ordinary gener- ating function of the number of complete subgraphs (cliques) of G. In this paper, we introduce a new vertex-weighted version of these polyno- mials. We also show that these weighted clique polynomials have always a real root provided that the weights are non-negative real numbers. As an application, we obtain a no-homomorphism criteria based on the largest real root of our vertex-weighted clique polynomial.