Clique Number

The clique number of a graph , denoted , is the number of vertices in a maximum clique of . Equivalently, it is the size of a largest clique or maximal clique of .

For an arbitrary graph,

where  is the degree of graph vertex . In addition, the chromatic number  of a graph  is equal to or greater than its clique number , i.e.,

The following table lists the clique numbers for some named graphs.

graph
complete graph
Coxeter graph	2
cubical graph	2
cycle graph	{3 if n=3; 2 otherwise" src="https://mathworld.wolfram.com/images/equations/CliqueNumber/Inline15.svg" style="height:68px; width:122px" />
Desargues graph	2
dodecahedral graph	2
Dyck graph	2
Folkman graph	2
Frucht graph	3
Grötzsch Graph	2
Heawood graph	2
Herschel graph	2
Icosahedral graph	3
Möbius-Kantor graph	2
octahedral graph	3
Pappus graph	2
Petersen graph	2
star graph	2
tetrahedral graph	4
wheel graph	{4 if n=4; 3 otherwise" src="https://mathworld.wolfram.com/images/equations/CliqueNumber/Inline17.svg" style="height:68px; width:122px" />

The following table gives the number  of -node graphs having clique number  for small .

	OEIS
1		1, 1, 1, 1, 1, 1, 1, 1, ...
2	A052450	0, 1, 2, 6, 13, 37, 106, 409, 1896, ...
3	A052451	0, 0, 1, 3, 15, 82, 578, 6021, 101267, ...
4	A052452	0, 0, 0, 1, 4, 30, 301, 4985, 142276, ...
5	A077392	0, 0, 0, 0, 1, 5, 51, 842, 27107, ...
6	A077393	0, 0, 0, 0, 0, 1, 6, 80, 1995, ...
7	A077394	0, 0, 0, 0, 0, 0, 1, 7, 117, ...
8		0, 0, 0, 0, 0, 0, 0, 1, 8, ...

---

REFERENCES

Aigner, M. "Turán's Graph Theorem." Amer. Math. Monthly 102, 808-816, 1995.

Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.

Hastad, J. "Clique Is Hard to Approximate Within ." Acta Math. 182, 105-142, 1999.

Sloane, N. J. A. Sequences A052450, A052451, A052452, A077392, A077393, and A077394 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

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

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

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

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

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

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

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

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