TOPICS
Search

Maximum Clique

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A maximum clique of a graph G is a clique (i.e., complete subgraph) of maximum possible size for G. Note that some authors refer to maximum cliques simply as "cliques." The size of the maximum clique is known as a graph's clique number, and the problem of finding the size of a clique for a given graph is an NP-complete problem (Skiena 1997).

A maximum clique in a given graph g can be found in the Wolfram Language using FindClique[g][[1]]. The command Sort[FindClique[g, Length /@ FindClique[g], All]] will find all maximum cliques.

A complete k-partite graph has maximum clique size k. The largest order-n graph which does not contain the complete graph K_p as a subgraph is called the Turán's graph T(n,p-1) (Gross and Yellen 2006, pp. 476-477; note the slightly nonstandard indexing T(n,p) by Skiena 1990, p. 218 and Pemmaraju and Skiena 2003, pp. 247-248).

See also

Caveman Graph, Clique, Clique Graph, Clique Number, Complete Graph, Induced Subgraph, Maximal Clique Party Problem, Perfect Graph, Ramsey Number, Turán's Theorem

Explore with Wolfram|Alpha

References

Bellare, M.; Goldreich, O.; and Sudan, M. "Free Bits, PCPs, and Non-Approximability--Towards Tight Results." SIAM J. Comput. 27, 804-915, 1998.Cormen, T.; Leiserson, C.; and Rivest, R. Introduction to Algorithms. Cambridge, MA: MIT Press, 1990.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Karp, R. M. "Reducibility Among Combinatorial Problems." In Complexity of Computer Calculations (Ed. R. Miller and J. Thatcher). New York: Plenum, pp. 85-103, 1972.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 476-477, 2006.Manber, U. Introduction to Algorithms: A Creative Approach. Reading, MA: Addison-Wesley, 1989.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.Sloane, N. J. A. Sequence A005289/M3440 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

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

Subject classifications