Clique Polynomial
المؤلف:
Fisher, D. C. and Solow, A. E.
المصدر:
"Dependence Polynomials." Disc. Math. 82
الجزء والصفحة:
...
17-4-2022
2055
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 |
![<span style=]() {(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  |
![<span style=]() {(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 |
![<span style=]() {(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 |
![<span style=]() {(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 |
![<span style=]() {(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  |
![<span style=]() {(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  |
![<span style=]() {(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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
