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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

المجمَع العلمي يطلق الدورة التطويرية الخامسة لمعلمي التربية الإسلامية ومدرسيها في النجف الأشرف

خدمات إنسانية متنوّعة تقدّمها شعبة الشهداء والجرحى في مختلف المحافظات

قسم العلاقات العامة يطلق فعاليات مخيم البذرة الواعدة الخاص بأبناء المنتسبين

جامعة العميد تنظم سلسلة دورات تطويرية لملاكاتها الإدارية

المزيد

الآخبار الصحية

اختراق علمي.. دواء يؤخر ظهور السكري من النوع الأول لسنوات

هذا ما يحدث لجسمك إن أهملت نظافة فراشك

لماذا تعتبر النساء أكثر عرضة للإصابة بألزهايمر من الرجال؟

لماذا يحذر الخبراء من الإفراط في تناول الفراولة؟

المزيد

الآخبار التكنلوجية

السيارات الكهربائية أنظف بنسبة 73% من سيارات الوقود

سيارة لوسِد الكهربائية تدخل "غينيس" بأطول مدى في العالم

نظرية جديدة تنسف كل ما نعرفه عن تشكل أول قارة في الأرض

منذ 37 ألف عام.. دراسة تكشف "أقدم أمراض" أصابت البشر

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength