TOPICS
Search

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

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

(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.

graph C(x)
Andrásfai graph A_n 1+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 graph 3nx^2+2nx+1
crown graph n(n-1)x^2+2nx+1
cycle graph C_n [画像:{(1+x)^3forn=3 ; 1+nx+nx^2 otherwise]
empty graph K^__n nx+1
folded cube graph [画像:{(x+1)^(2(n-1)) for n=2,3; 1+2^(n-2)x(nx+2) otherwise]
gear graph 3nx^2+x(2n+1)x+1
grid graph P_m×P_n 1+mnx+(2mn-m-n)x^2
grid graph P_l×P_m×P_n 1+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_n 2^(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 graph 1+mnx+2(2mn-3m-3n+4)x^2
ladder graph P_2 square P_n 1-2x^2+nx(2+3x)
ladder rung graph nP_2 1+nx(2+x)
Möbius ladder M_n 1+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 graph nx(1+x)^2+(1+x)^n
sunlet graph C_n circledot K_1 1+2nx(1+x)
transposition graph 1+n!x+1/4n!n(n-1)x^2
triangular grid graph 1/2(1+x)(2+nx(3+n+2nx))
web graph for n>3 1+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.

graph order recurrence
Andrásfai graph A_n 4 p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
barbell graph 2 p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
book graph S_(n+1) square P_2 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
cocktail party graph K_(n×2) 1 p_n(x)=(2x+1)p_(n-1)(x)
complete bipartite graph K_(n,n) 3 p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
complete graph K_n 1 p_n(x)=(x+1)p_(n-1)(x)
(2n)-crossed prism graph 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
crown graph 3 p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
cycle graph C_n for n>=4 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
empty graph K^__n 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
folded cube graph 3 p_n(x)=4p_(n-3)(x)-8p_(n-2)(x)+5p_(n-1)(x)
gear graph 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
grid graph P_n×P_n 3 p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
grid graph P_n×P_n×P_n 4 p_n(x)=-p_(n-4)(x)+4p_(n-3)(x)-6p_(n-2)(x)+4p_(n-1)(x)
hypercube graph Q_n 3 p_n(x)=4p_(n-3)(x)-8p_(n-2)(x)+5p_(n-1)(x)
n×n-king graph 3 p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
n×n-knight graph 3 p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
ladder graph P_2 square P_n 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
ladder rung graph nP_2 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
Möbius ladder M_n 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
path graph P_n 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
prism graph Y_n 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
star graph S_n 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
sun graph 3 p_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_1 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
triangular grid graph 3 p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
wheel graph W_n 2 p_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.

Referenced on Wolfram|Alpha

Clique Polynomial

Cite this as:

Weisstein, Eric W. "Clique Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CliquePolynomial.html

Subject classifications

AltStyle によって変換されたページ (->オリジナル) /