TOPICS

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 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.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."

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