TOPICS
Clique
A clique of a graph
is a complete subgraph of
, and the clique of largest possible size is referred to as amaximum clique (which has size known as the (upper)clique number
). However, care is needed since maximum cliques are often called simply "cliques" (e.g., Harary 1994). Amaximal 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 ofgraph theory and combinatorics, including graph coloring and the theory oferror-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.
Theclique polynomial is of a graph
is defined as
 |
where
is the number of cliques of size
, with
,
equal to thevertex count of
,
equal to theedge count of
, etc.
In theWolfram Language, the commandFindClique[g][[1]] can be used to find amaximum clique, andFindClique[g,Length /@FindClique[g],All] to find allmaximum cliques. Similarly,FindClique[g,Infinity] can be used to find amaximal clique, andFindClique[g,Infinity,All] to find all maximal cliques. To find all cliques, enumerate all vertex subsets
and select those for whichCompleteGraphQ[g,s] is true.
In general,FindClique[g,n] can be used to find amaximal 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, andFindClique[g,
n
,All] to find all such cliques.
The numbers of cliques, equal to theclique 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 theclique 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 gasket 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.
-
See also
Clique Covering,Clique Covering Number,Clique Number,Clique Polynomial,Lower Clique Number,Maximal Clique,Maximum CliqueExplore with Wolfram|Alpha
More things to try:
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 inImplementing 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 inThe Algorithm Design Manual. New York: Springer-Verlag, pp. 144 and 312-314, 1997.Referenced on Wolfram|Alpha
CliqueCite this as:
Weisstein, Eric W. "Clique." FromMathWorld--AWolfram Resource.https://mathworld.wolfram.com/Clique.html