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.

graphC(x)
Andrásfai graph A_n1+1/2(3n-1)x(nx+2)
antiprism graph{(2x+1)(4x^2+6x+1) for n=3; nx^2+nx+1 otherwise
barbell graph-1+x^2+2(1+x)^n
book graph S_(n+1) square P_2(3n+1)x^2+x^2+2(n+1)x+1
cocktail party graph K_(n×2)(1+2x)^n
complete bipartite graph K_(m,n)(1+mx)(1+nx)
complete graph K_n(1+x)^n
complete tripartite graph K_(l,m,n)(1+lx)(1+mx)(1+nx)
crossed prism graph3nx^2+2nx+1
crown graphn(n-1)x^2+2nx+1
cycle graph C_n{(1+x)^3forn=3 ; 1+nx+nx^2 otherwise
empty graph K^__nnx+1
folded cube graph{(x+1)^(2(n-1)) for n=2,3; 1+2^(n-2)x(nx+2) otherwise
gear graph3nx^2+x(2n+1)x+1
grid graph P_m×P_n1+mnx+(2mn-m-n)x^2
grid graph P_l×P_m×P_n1+lmnx+(3lmn-lm-ln-mn)x^2
helm graph{(1+x)(1+6x+3x^2+x^3) for n=3; (1+x)(1+2nx+nx^2) otherwise
hypercube graph Q_n2^(n-1)x(2+nx)+1
m×n-king graph{(1+x)^2(1+(n-1)x(2+x)) for m=2; (1+x)(1+(mn-1)x+3(m-1)(n-1)x^2+(m-1)(n-1)x^3) otherwise
m×n-knight graph1+mnx+2(2mn-3m-3n+4)x^2
ladder graph P_2 square P_n1-2x^2+nx(2+3x)
ladder rung graph nP_21+nx(2+x)
Möbius ladder M_n1+nx(2+3x)
path graph P_n(1+x)(1+(-1+n)x)
prism graph Y_n{(2x+1)(x^2+4x+1) for n=3; 1+nx(2+3x) otherwise
star graph S_n(1+x)(1+(-1+n)x)
sun graphnx(1+x)^2+(1+x)^n
sunlet graph C_n circledot K_11+2nx(1+x)
transposition graph1+n!x+1/4n!n(n-1)x^2
triangular grid graph1/2(1+x)(2+nx(3+n+2nx))
web graph for n>31+3nx+4nx^2
wheel graph W_n{(1+x)^4 for n=4; (1+x)(1+(-1+n)x(1+x)) otherwise

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

graphorderrecurrence
Andrásfai graph A_n4p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
barbell graph2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
book graph S_(n+1) square P_22p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
cocktail party graph K_(n×2)1p_n(x)=(2x+1)p_(n-1)(x)
complete bipartite graph K_(n,n)3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
complete graph K_n1p_n(x)=(x+1)p_(n-1)(x)
(2n)-crossed prism graph2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
crown graph3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
cycle graph C_n for n>=42p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
empty graph K^__n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
folded cube graph3p_n(x)=4p_(n-3)(x)-8p_(n-2)(x)+5p_(n-1)(x)
gear graph2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
grid graph P_n×P_n3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
grid graph P_n×P_n×P_n4p_n(x)=-p_(n-4)(x)+4p_(n-3)(x)-6p_(n-2)(x)+4p_(n-1)(x)
hypercube graph Q_n3p_n(x)=4p_(n-3)(x)-8p_(n-2)(x)+5p_(n-1)(x)
n×n-king graph3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
n×n-knight graph3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
ladder graph P_2 square P_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
ladder rung graph nP_22p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
Möbius ladder M_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
path graph P_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
prism graph Y_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
star graph S_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
sun graph3p_n(x)=(x+1)p_(n-3)(x)-(2x+3)p_(n-2)(x)+(x+3)p_(n-1)(x)
sunlet graph C_n circledot K_12p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
triangular grid graph3p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
wheel graph W_n2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)

See also

Clique, Clique Number

Explore with Wolfram|Alpha

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