Clique Number
المؤلف:
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,
الجزء والصفحة:
...
4-3-2022
2185
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  |
![<span style=]() {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  |
![<span style=]() {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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
