[go: up one dir, main page]
TOPICS
Search

Clique

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Clique

A clique of a graph G is a complete subgraph of G, and the clique of largest possible size is referred to as a maximum clique (which has size known as the (upper) clique number omega(G)). However, care is needed since maximum cliques are often called simply "cliques" (e.g., Harary 1994). A maximal clique is a clique that cannot be extended by including one more adjacent vertex, meaning it is not a subset of a larger clique. Maximum cliques are therefore maximal cliqued (but not necessarily vice versa).

Cliques arise in a number of areas of graph theory and combinatorics, including graph coloring and the theory of error-correcting codes.

A clique of size k is called a k-clique (though this term is also sometimes used to mean a maximal set of vertices that are at a distance no greater than k from each other). 0-cliques correspond to the empty set (sets of 0 vertices), 1-cliques correspond to vertices, 2-cliques to edges, and 3-cliques to 3-cycles.

The clique polynomial is of a graph G is defined as

C_G(x)=sum_(k=0)^(omega(G))c_kx^k,

where c_k is the number of cliques of size k, with c_0=1, c_1=|G| equal to the vertex count of G, c_2=m(G) equal to the edge count of G, etc.

In the Wolfram Language, the command FindClique[g][[1]] can be used to find a maximum clique, and FindClique[g, Length /@ FindClique[g], All] to find all maximum cliques. Similarly, FindClique[g, Infinity] can be used to find a maximal clique, and FindClique[g, Infinity, All] to find all maximal cliques. To find all cliques, enumerate all vertex subsets s and select those for which CompleteGraphQ[g, s] is true.

In general, FindClique[g, n] can be used to find a maximal clique containing at least n vertices, FindClique[g, n, All] to find all such cliques, FindClique[g, {n}] to find a clique containing at exactly n vertices, and FindClique[g, {n}, All] to find all such cliques.

The numbers of cliques, equal to the clique polynomial evaluated at x=1, for various members of graph families are summarized in the table below, where the trivial 0-clique represented by the initial 1 in the clique polynomial is included in each count.

graph familyOEISnumber of cliques
alternating group graphA308599X, 2, 8, 45, 301, 2281, ...
Andrásfai graphA1150674, 11, 21, 34, 50, 69, 91, ...
n×n antelope graphA3086002, 5, 10, 17, 34, 61, 98, ...
antiprism graphA017077X, X, 27, 33, 41, 49, 57, 65, ...
Apollonian networkA20524816, 40, 112, 328, 976, 2920, ...
barbell graphA000079X, X, 16, 32, 64, 128, 256, 512, ...
n×n bishop graphA1831562, 7, 22, 59, 142, 319, ...
n×n black bishop graphA2959092, 4, 14, 30, 82, 160, 386, ...
book graph S_(n+1) square P_2A0168979, 14, 19, 24, 29, 34, 39, 44, ...
Bruhat graphA1391492, 4, 13, 61, 361, 2521, 20161, ...
centipede graphA0085864, 8, 12, 16, 20, 24, 28, 32, 36, ...
cocktail party graph K_(n×2)A0002443, 9, 27, 81, 243, 729, 2187, ...
complete graph K_nA0000792, 4, 8, 16, 32, 64, 128, 256, ...
complete bipartite graph K_(n,n)A0002904, 9, 16, 25, 36, 49, 64, 81, 100, ...
complete tripartite graph K_(n,n,n)A0005788, 27, 64, 125, 216, 343, 512, ...
2n-crossed prism graphA017281X, 21, 31, 41, 51, 61, 71, ...
crown graph K_2 square K_n^_A002061X, X, 13, 21, 31, 43, 57, 73, 91, ...
cube-connected cycle graphA295926X, X, 69, 161, 401, 961, 2241, 5121, ...
cycle graph C_nA308602X, X, 8, 9, 11, 13, 15, 17, 19, ...
dipyramidal graphA308603X, X, 24, 27, 33, 39, 45, 51, 57, 63, ...
empty graph K^__nA0000272, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
Fibonacci cube graphA2919164, 6, 11, 19, 34, 60, 106, 186, ...
n×n fiveleaper graphA308604X, 4, 16, 25, 57, 129, 289, 641, 1409, ...
folded cube graphA2959213, 15, 24, 56, ...
gear graphA016873X, X, 17, 22, 27, 32, 37, 42, 47, 52, ...
grid graph P_n square P_nA0561052, 9, 22, 41, 66, 97, 134, 177, 226, 281, ...
grid graph P_n square P_n square P_nA2959072, 21, 82, 209, 426, 757, 1226, 1857, ...
halved cube graphA2959222, 4, 16, 81, 393, 1777, ...
Hanoi graphA2959118, 25, 76, 229, 688, ...
helm graphA016933X, X, 22, 26, 32, 38, 44, 50, 56, ...
hypercube graph Q_nA1327504, 9, 21, 49, 113, 257, 577, 1281, 2817, ...
Keller graphA2959025, 57, 14833, 2290312801, ...
n×n king graphA2959062, 16, 50, 104, 178, 272, 386, ...
n×n knight graphA2959052, 5, 18, 41, 74, 117, 170, 233, 306, 389, ...
ladder graph P_2 square P_nA0168974, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, ...
ladder rung graph nP_2A0167774, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, ...
Menger sponge graphA29220945, 1073, 22977, ...
Möbius ladder M_nA016861X, X, 16, 21, 26, 31, 36, 41, 46, 51, ...
Mycielski graphA1991092, 4, 11, 32, 95, 284, 851, 2552, 7655, ...
odd graph O_nA2959342, 8, 26, 106, 442, 1849, 7723, ...
pan graphA005408X, X, 10, 11, 13, 15, 17, 19, 21, 23, ...
path graph P_nA0058432, 4, 6, 8, 10, 12, 14, 16, 18, 20, ...
path complement graph P^__nA0000452, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
permutation star graphA1391492, 4, 13, 61, 361, 2521, ...
polygon diagonal intersection graphA300524X, X, 8, 18, 41, 80, 169, 250, ...
prism graph K_2 square C_nA016861X, X, 18, 21, 26, 31, 36, 41, 46, 51, ...
n×n queen graphA2959032, 16, 94, 293, 742, 1642, 3458, 7087, ...
rook graph K_n square K_nA2889582, 9, 34, 105, 286, 721, 1730, ...
rook complement graph K_n square K_n^_A0027202, 7, 34, 209, 1546, 13327, 130922, ...
Sierpiński carpet graphA29593217, 153, 1289, 10521, ...
Sierpiński gasket graphA2959338, 20, 55, 160, 475, ...
Sierpiński tetrahedron graphA2925376, 59, 227, 899, 3587, 14339, ...
star graph S_nA0058432, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, ...
sun graphA295904X, X, 20, 32, 52, 88, 156, 288, 548, ...
sunlet graph C_n circledot K_1A016813X, X, 14, 17, 21, 25, 29, 33, 37, 41, 45, ...
tetrahedral graphA289837X, X, X, X, X, 261, 757, 2003, 5035, ...
torus grid graph C_n square C_nA056107X, X, 34, 49, 76, 109, 148, 193, ...
transposition graphA3086062, 4, 16, 97, 721, 6121, ...
triangular graphA290056X, 2, 8, 27, 76, 192, 456, 1045, ...
triangular grid graphA2426588, 20, 38, 62, 92, 128, 170, 218, ...
triangular snake graph TS_nA0167892, X, 8, X, 14, X, 20, X, 26, X, 32, X, ...
web graphA016993X, X, 24, 29, 36, 43, 50, 57, 64, 71, 78, ...
wheel graph W_nA308607X, X, X, 16, 18, 22, 26, 30, 34, 38, 42, 46, ...
n×n white bishop graphA295910X, 4, 9, 30, 61, 160, 301, 71, ...

Closed forms for some of these are summarized in the table below.

graph familynumber of cliques
Andrásfai graph1/2(n+2)(3n-1)
antiprism graph{26 for n=3; 8n for n>=4
book graph S_(n+1) square P_25n+3
cocktail party graph K_(n×2)3^n-1
complete bipartite graph K_(n,n)2^n-1
complete graph K_nn(n+2)
complete tripartite graph K_(n,n,n)n(n^2+3n+3)
2n-crossed prism graph10n
cycle graph C_n{7 for n=3; 2n for n>=4
empty graph K^__nn
gear graph5n+11
helm graph{21 for n=3; 8n for n>=4
hypercube graph Q_n2^(n-1)(n+2)
ladder graph5n-2
ladder rung graph nP_23n
Möbius ladder M_n5(n+2)
pan graph{9 for n=3; 2(n+1) for n>=4
path graph P_n2n-1
prism graph Y_n{17 for n=3; 5n for n>=4
star graph S_n2n-1
sun graph2^n+4n-1
sunlet graph C_n circledot K_1{13 for n=3; 4n for n>=4
web graph{23 for n=3; 7n for n>=4
wheel graph W_n{15 for n=3; 4n-3 for n>=4

See also

Clique Covering, Clique Covering Number, Clique Number, Clique Polynomial, Lower Clique Number, Maximal Clique, Maximum Clique

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 247-248, 2003.Skiena, S. "Maximum Cliques." §5.6.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 215 and 217-218, 1990.Skiena, S. S. "Clique and Independent Set" and "Clique." §6.2.3 and 8.5.1 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 144 and 312-314, 1997.

Referenced on Wolfram|Alpha

Clique

Cite this as:

Weisstein, Eric W. "Clique." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Clique.html

Subject classifications