TOPICS
Search

Maximum Clique

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A maximum clique of a graph G is a clique (i.e., a complete subgraph) of maximum possible size for G. Some authors refer to maximum cliques simply as "cliques." The size of a maximum clique is the clique number. Computing this size is an NP-hard problem; the decision problem of whether a graph contains a clique of size at least k 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 with k nonempty parts has maximum clique size k. A graph on n vertices having the maximum possible edge count among those that do 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.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.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Karp, R. M. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972 (Ed. R. E. Miller and J. W. Thatcher). New York: Plenum, pp. 85-103, 1972.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."

Referenced on Wolfram|Alpha

Maximum Clique

Cite this as:

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

Subject classifications