Clique Polynomial

The clique polynomial C_G(x) for the graph G is defined as the polynomial


where omega(G) is the clique number of G, the coefficient of x_k for k>0 is the number of cliques c_k in the graph, and the constant term is 1 (Hoede and Li 1994, Hajiabolhassan and Mehrabadi 1998). Hajiabolhassan and Mehrabadi (1998) showed that C_G(x) always has a real root.

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

C_G(x) is related to the independence polynomial by


where G^_ denotes the graph complement (Hoede and Li 1994).

This polynomial is similar to the dependence polynomial defined as


(Fisher and Solow 1990), with the two being related by


The following table summarizes clique polynomials for some common classes of graphs.

The following table summarizes the recurrence relations for clique polynomials for some simple classes of graphs.

See also

Clique, Clique Number

Explore with Wolfram|Alpha


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.

Cite this as:

Weisstein, Eric W. "Clique Polynomial." From MathWorld--A Wolfram Web Resource.

Subject classifications