A Generalization of Clique Polynomials and Graph Homomorphism

Abstract

The clique polynomial of a graph
G is the ordinary generating function of the number of
complete subgraphs (cliques) of $G$. In this paper, we introduce a new vertex-weighted version of these
polynomials. 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.