تسجيل الدخول

تسجيل

Clique Polynomial

المؤلف:  Fisher, D. C. and Solow, A. E.

المصدر:  "Dependence Polynomials." Disc. Math. 82

الجزء والصفحة:  ...

17-4-2022

2586

Clique Polynomial

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 a graph with  vertices, 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.

 is related to the independence polynomial by

(2)

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

This polynomial is similar to the dependence polynomial defined as

(3)

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

(4)

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

graph
Andrásfai graph
antiprism graph	{(2x+1)(4x^2+6x+1) for n=3; nx^2+nx+1 otherwise" src="https://mathworld.wolfram.com/images/equations/CliquePolynomial/Inline18.svg" style="height:72px; width:376px" />
barbell graph
book graph
cocktail party graph
complete bipartite graph
complete graph
complete tripartite graph
crossed prism graph
crown graph
cycle graph	{(1+x)^3forn=3 ; 1+nx+nx^2 otherwise" src="https://mathworld.wolfram.com/images/equations/CliquePolynomial/Inline33.svg" style="height:68px; width:282px" />
empty graph
folded cube graph	{(x+1)^(2(n-1)) for n=2,3; 1+2^(n-2)x(nx+2) otherwise" src="https://mathworld.wolfram.com/images/equations/CliquePolynomial/Inline36.svg" style="height:68px; width:347px" />
gear graph
grid graph
grid graph
helm graph	{(1+x)(1+6x+3x^2+x^3) for n=3; (1+x)(1+2nx+nx^2) otherwise" src="https://mathworld.wolfram.com/images/equations/CliquePolynomial/Inline42.svg" style="height:76px; width:403px" />
hypercube graph
-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" src="https://mathworld.wolfram.com/images/equations/CliquePolynomial/Inline46.svg" style="height:72px; width:808px" />
-knight graph
ladder graph
ladder rung graph
Möbius ladder
path graph
prism graph	{(2x+1)(x^2+4x+1) for n=3; 1+nx(2+3x) otherwise" src="https://mathworld.wolfram.com/images/equations/CliquePolynomial/Inline58.svg" style="height:72px; width:357px" />
star graph
sun graph
sunlet graph
transposition graph
triangular grid graph
web graph for
wheel graph	{(1+x)^4 for n=4; (1+x)(1+(-1+n)x(1+x)) otherwise" src="https://mathworld.wolfram.com/images/equations/CliquePolynomial/Inline69.svg" style="height:68px; width:449px" />

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

graph	order	recurrence
Andrásfai graph	4
barbell graph	2
book graph	2
cocktail party graph	1
complete bipartite graph	3
complete graph	1
-crossed prism graph	2
crown graph	3
cycle graph  for	2
empty graph	2
folded cube graph	3
gear graph	2
grid graph	3
grid graph	4
hypercube graph	3
-king graph	3
-knight graph	3
ladder graph	2
ladder rung graph	2
Möbius ladder	2
path graph	2
prism graph	2
star graph	2
sun graph	3
sunlet graph	2
triangular grid graph	3
wheel graph	2

---

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.