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
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.
Closed forms for some of these are summarized in the table below.
See also
Clique Covering, Clique Covering Number, Clique Number, Clique Polynomial, Lower Clique Number, Maximal Clique, Maximum CliqueExplore 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
CliqueCite this as:
Weisstein, Eric W. "Clique." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Clique.html