Clique (graph theory)

From Wikipedia, the free encyclopedia

K₅, a complete graph. If a subgraph looks like this, the vertices in that subgraph form a clique of size 5.

A graph with 6 vertices and 7 edges. On this graph vertices 1, 2, 5 is the only clique of size 3.

In graph theory, a clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph). The size of a clique is the number of vertices it contains.

Finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete.

The opposite of a clique is an independent set, in the sense that every clique corresponds to an independent set in the complement graph.

The term presumably comes from the idea that, if the vertices represent people and the edges represent the relation 'knows', then everyone knows everyone else, thus forming a clique.

The size of the largest clique in a graph G is of theoretical importance and denoted ω(G).^[1]

[edit] Notes

[edit] See also

• Glossary of graph theory
• Maximum common subgraph isomorphism problem
• Maximal clique
• Clique complex, an abstract simplicial complex X(G) with a simplex for every clique in a graph G
• Simplex graph, an undirected graph κ(G) with a vertex for every clique in a graph G

[edit] References

• Godsil, Chris; Gordon Royle (2004) [1949]. Algebraic graph theory. New York: Springer. ISBN 0-387-95220-9. 

[edit] External links

• Cliquer, a set of C routines for finding cliques in an arbitrary weighted graph.