TOPICS
Search

Clique Polynomial


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

 C_G(x)=1+sum_(k=1)^(omega(G))c_kx^k,
(1)

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

 C_G(x)=I_(G^_)(x),
(2)

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

This polynomial is similar to the dependence polynomial defined as

 D_G(x)=1+sum_(k=1)^(omega(G))(-1)^kc_kx^k
(3)

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

 C_G(x)=D_G(-x).
(4)

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

WolframAlpha

More things to try:

References

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. https://mathworld.wolfram.com/CliquePolynomial.html

Subject classifications