A clique of a graph is its maximal complete subgraph (Harary 1994, p. 20), although some authors define
a clique as any complete subgraph and then refer to "maximum cliques" (Skiena
1990, p. 217). The problem of finding the size of a clique for a given graph is an NP-complete
problem (Skiena 1997).
Cliques arise in a number of areas of graph theory and combinatorics, including the theory of error-correcting codes. The command MaximumClique[g] in the Mathematica package Combinatorica`) finds
an example of a largest clique in a given graph.
The number of graphs on  nodes having 3 cliques are 0, 0, 1, 4,
12, 31, 67, ... (Sloane's A005289). A complete
k-partite graph has maximum clique size  . The largest order
 graph which does not contain the complete graph  as a subgraph is called the Turán's
graph  (Skiena 1990, p. 218).
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.
Manber, U. Introduction to Algorithms: A Creative Approach. Reading,
MA: Addison-Wesley, 1989.
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."
|
Contact the MathWorld Team
