The clique polynomial
for the graph
is defined as the polynomial

(1)

where
is the clique number of , the coefficient of for is the number of cliques in the graph, and the constant term
is 1 (Hoede and Li 1994, Hajiabolhassan and Mehrabadi 1998). Hajiabolhassan and Mehrabadi
(1998) showed that
always has a real root.

The coefficient
is the vertex count, is the edge count, and is the triangle count in a graph.

Fisher, D. C. and Solow, A. E. "Dependence Polynomials." Disc. Math.82, 251-258, 1990.Goldwurm,
M. and Santini, M. "Clique Polynomials Have a Unique Root of Smallest Modulus."
Informat. Proc. Lett.75, 127-132, 2000.Hajiabolhassan,
H. and Mehrabadi, M. L. "On Clique Polynomials." Australas. J.
Combin.18, 313-316, 1998.Hoede, C. and Li, X. "Clique
Polynomials and Independent Set Polynomials of Graphs." Discr. Math.125,
219-228, 1994.Levit, V. E. and Mandrescu, E. "The Independence
Polynomial of a Graph--A Survey." In Proceedings of the 1st International
Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005
(Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki,
Greece: Aristotle Univ., pp. 233-254, 2005.