Clique

 

 

A clique of a graph  is a complete subgraph of , and the clique of largest possible size is referred to as a maximum clique (which has size known as the clique number ). However, care is needed since maximum cliques are often called simply "cliques" (e.g., Harary 1994). A maximal clique is a clique that cannot be extended by including one more adjacent vertex, meaning it is not a subset of a larger clique. Maximum cliques are therefore maximal cliqued (but not necessarily vice versa).

Cliques arise in a number of areas of graph theory and combinatorics, including graph coloring and the theory of error-correcting codes.

A clique of size  is called a -clique (though this term is also sometimes used to mean a maximal set of vertices that are at a distance no greater than  from each other). 0-cliques correspond to the empty set (sets of 0 vertices), 1-cliques correspond to vertices, 2-cliques to edges, and 3-cliques to 3-cycles.

The clique polynomial is of a graph  is defined as

where  is the number of cliques of size , with ,  equal to the vertex count of ,  equal to the edge count of , etc.

In the Wolfram Language, the command FindClique[g][[1]] can be used to find a maximum clique, and FindClique[g, Length /@ FindClique[g], All] to find all maximum cliques. Similarly, FindClique[g, Infinity] can be used to find a maximal clique, and FindClique[g, Infinity, All] to find all maximal cliques. To find all cliques, enumerate all vertex subsets  and select those for which CompleteGraphQ[g, s] is true.

In general, FindClique[g, n] can be used to find a maximal clique containing at least  vertices, FindClique[g, n, All] to find all such cliques, FindClique[g, n] to find a clique containing at exactly  vertices, and FindClique[g, n, All] to find all such cliques.

The numbers of cliques, equal to the clique polynomial evaluated at , for various members of graph families are summarized in the table below, where the trivial 0-clique represented by the initial 1 in the clique polynomial is included in each count.

graph family	OEIS	number of cliques
alternating group graph	A308599	X, 2, 8, 45, 301, 2281, ...
Andrásfai graph	A115067	4, 11, 21, 34, 50, 69, 91, ...
antelope graph	A308600	2, 5, 10, 17, 34, 61, 98, ...
antiprism graph	A017077	X, X, 27, 33, 41, 49, 57, 65, ...
Apollonian network	A205248	16, 40, 112, 328, 976, 2920, ...
barbell graph	A000079	X, X, 16, 32, 64, 128, 256, 512, ...
bishop graph	A183156	2, 7, 22, 59, 142, 319, ...
black bishop graph	A295909	2, 4, 14, 30, 82, 160, 386, ...
book graph	A016897	9, 14, 19, 24, 29, 34, 39, 44, ...
Bruhat graph	A139149	2, 4, 13, 61, 361, 2521, 20161, ...
centipede graph	A008586	4, 8, 12, 16, 20, 24, 28, 32, 36, ...
cocktail party graph	A000244	3, 9, 27, 81, 243, 729, 2187, ...
complete graph	A000079	2, 4, 8, 16, 32, 64, 128, 256, ...
complete bipartite graph	A000290	4, 9, 16, 25, 36, 49, 64, 81, 100, ...
complete tripartite graph	A000578	8, 27, 64, 125, 216, 343, 512, ...
-crossed prism graph	A017281	X, 21, 31, 41, 51, 61, 71, ...
crown graph	A002061	X, X, 13, 21, 31, 43, 57, 73, 91, ...
cube-connected cycle graph	A295926	X, X, 69, 161, 401, 961, 2241, 5121, ...
cycle graph	A308602	X, X, 8, 9, 11, 13, 15, 17, 19, ...
dipyramidal graph	A308603	X, X, 24, 27, 33, 39, 45, 51, 57, 63, ...
empty graph	A000027	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
Fibonacci cube graph	A291916	4, 6, 11, 19, 34, 60, 106, 186, ...
fiveleaper graph	A308604	X, 4, 16, 25, 57, 129, 289, 641, 1409, ...
folded cube graph	A295921	3, 15, 24, 56, ...
gear graph	A016873	X, X, 17, 22, 27, 32, 37, 42, 47, 52, ...
grid graph	A056105	2, 9, 22, 41, 66, 97, 134, 177, 226, 281, ...
grid graph	A295907	2, 21, 82, 209, 426, 757, 1226, 1857, ...
halved cube graph	A295922	2, 4, 16, 81, 393, 1777, ...
Hanoi graph	A295911	8, 25, 76, 229, 688, ...
helm graph	A016933	X, X, 22, 26, 32, 38, 44, 50, 56, ...
hypercube graph	A132750	4, 9, 21, 49, 113, 257, 577, 1281, 2817, ...
Keller graph	A295902	5, 57, 14833, 2290312801, ...
king graph	A295906	2, 16, 50, 104, 178, 272, 386, ...
knight graph	A295905	2, 5, 18, 41, 74, 117, 170, 233, 306, 389, ...
ladder graph	A016897	4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, ...
ladder rung graph	A016777	4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, ...
Menger sponge graph	A292209	45, 1073, 22977, ...
Möbius ladder	A016861	X, X, 16, 21, 26, 31, 36, 41, 46, 51, ...
Mycielski graph	A199109	2, 4, 11, 32, 95, 284, 851, 2552, 7655, ...
odd graph	A295934	2, 8, 26, 106, 442, 1849, 7723, ...
pan graph	A005408	X, X, 10, 11, 13, 15, 17, 19, 21, 23, ...
path graph	A005843	2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ...
path complement graph	A000045	2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
permutation star graph	A139149	2, 4, 13, 61, 361, 2521, ...
polygon diagonal intersection graph	A300524	X, X, 8, 18, 41, 80, 169, 250, ...
prism graph	A016861	X, X, 18, 21, 26, 31, 36, 41, 46, 51, ...
queen graph	A295903	2, 16, 94, 293, 742, 1642, 3458, 7087, ...
rook graph	A288958	2, 9, 34, 105, 286, 721, 1730, ...
rook complement graph	A002720	2, 7, 34, 209, 1546, 13327, 130922, ...
Sierpiński carpet graph	A295932	17, 153, 1289, 10521, ...
Sierpiński sieve graph	A295933	8, 20, 55, 160, 475, ...
Sierpiński tetrahedron graph	A292537	6, 59, 227, 899, 3587, 14339, ...
star graph	A005843	2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, ...
sun graph	A295904	X, X, 20, 32, 52, 88, 156, 288, 548, ...
sunlet graph	A016813	X, X, 14, 17, 21, 25, 29, 33, 37, 41, 45, ...
tetrahedral graph	A289837	X, X, X, X, X, 261, 757, 2003, 5035, ...
torus grid graph	A056107	X, X, 34, 49, 76, 109, 148, 193, ...
transposition graph	A308606	2, 4, 16, 97, 721, 6121, ...
triangular graph	A290056	X, 2, 8, 27, 76, 192, 456, 1045, ...
triangular grid graph	A242658	8, 20, 38, 62, 92, 128, 170, 218, ...
triangular snake graph	A016789	2, X, 8, X, 14, X, 20, X, 26, X, 32, X, ...
web graph	A016993	X, X, 24, 29, 36, 43, 50, 57, 64, 71, 78, ...
wheel graph	A308607	X, X, X, 16, 18, 22, 26, 30, 34, 38, 42, 46, ...
white bishop graph	A295910	X, 4, 9, 30, 61, 160, 301, 71, ...

Closed forms for some of these are summarized in the table below.

 

 

graph family	number of cliques
Andrásfai graph
antiprism graph
book graph
cocktail party graph
complete bipartite graph
complete graph
complete tripartite graph
-crossed prism graph
cycle graph
empty graph
gear graph
helm graph
hypercube graph
ladder graph
ladder rung graph
Möbius ladder
pan graph
path graph
prism graph
star graph
sun graph
sunlet graph
web graph
wheel graph

---

REFERENCES

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength