A Generalization of Clique Polynomials and Graph Homomorphism

Hossein Teimoori Faal, Mortaza Bayat


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.


Weighted Clique Polynomial; Blow-Up Graph; No-Homomorphism Criteria

Full Text: PDF


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.