Maximum Clique

Author

Eric W. Weisstein
September 30, 2025

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/MaximumClique.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/MaximumClique.html.

©2025 Wolfram Research, Inc. except for portions noted otherwise

Table

DateString[]

table=GraphDataCountTable["MaximumCliqueCount",{"Keller"->296100}]

TextGrid[OEISUpdates[table],Dividers->All]

Parametrized families

Andrasfai

=== MaximalCliqueCount

A000326

seq=Table[GraphData[{"Andrasfai",n},"MaximumCliqueCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//Factor

seq=Table[(3n-1)n/2,{n,20}]

LinearRecurrence[{3,-3,1},{1,5,12},20]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((x(-1-2 x))/(((-1+x))^3)),{x,0,20}],x]

PolygonalNumber[5,Range[0,20]]

Antiprism

=== MaximalCliqueCount

Entity["Graph",{"Antiprism",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Antiprism",n},"MaximumCliqueCount"],{n,3,25}]

Apollonian

=== MaximalCliqueCount

A003462

seq=Table[GraphData[{"Apollonian",n},"MaximumCliqueCount"],{n,6}]

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

seq=LinearRecurrence[{4,-2},{1,4},{0,20}]

FindGeneratingFunction[seq,x]

CoefficientList[Series[(x/(1-4 x+3 (x^2))),{x,0,20}],x]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"MaximumCliqueCount"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"MaximumCliqueCount"],{n,10}]

Book

=== MaximalCliqueCount

A016777

seq=Table[GraphData[{"Book",n},"MaximumCliqueCount"],{n,20}]

FindSequenceFunction[seq,n]

Centipede

=== MaximalCliqueCount

A005408

seq=Table[GraphData[{"Centipede",n},"MaximumCliqueCount"],{n,10}]

FindSequenceFunction[seq,n]

seq=2Range[0,20]+1

FindLinearRecurrence[seq]

LinearRecurrence[{2,-1},{1,3},20]

FindGeneratingFunction[seq,x]

CoefficientList[Series[((1+x)/(((-1+x))^2)),{x,0,20}],x]

CocktailParty

=== MaximalCliqueCount

A000079

seq=Table[GraphData[{"CocktailParty",n},"MaximumCliqueCount"],{n,20}]

FindSequenceFunction[seq,n]

Complete

=== MaximalCliqueCount

Entity["Graph",{"Complete",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Complete",n},"MaximumCliqueCount"],{n,20}]

CompleteBipartite m×n

=== MaximalCliqueCount

Entity["Graph",{"CompleteBipartite",{m,n}}]["MaximumCliqueCount"]

DeleteCases[Block[{m,n},Sort[{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],GraphData[#,"MaximumCliqueCount"],m n}&/@GraphData["CompleteBipartite"]]],{_,x_,x_}]

CompleteBipartite n×n

=== MaximalCliqueCount

Entity["Graph",{"CompleteBipartite",{n,n}}]["MaximumCliqueCount"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"MaximumCliqueCount"],{n,20}]

CompleteTripartite k×m×n

=== MaximalCliqueCount

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["MaximumCliqueCount"]

DeleteCases[Block[{k,m,n},Sort[{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],GraphData[#,"MaximumCliqueCount"],k m n}&/@GraphData["CompleteTripartite"]]],{_,x_,x_}]

CompleteTripartite n×n×n

=== MaximalCliqueCount

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["MaximumCliqueCount"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"MaximumCliqueCount"],{n,10}]

CrossedPrism

=== MaximalCliqueCount

A008588

seq=Table[GraphData[{"CrossedPrism",2n},"MaximumCliqueCount"],{n,2,10}]

FindSequenceFunction[seq,n-1]//Factor

CubeConnectedCycle

=== MaximalCliqueCount (for n > 3)

Entity["Graph",{"CubeConnectedCycle",n}]["MaximumCliqueCount"]

A167667

seq=Table[GraphData[{"CubeConnectedCycle",n},"MaximumCliqueCount"],{n,3,8}]

FindSequenceFunction[seq,n]

(seq=Table[Length@FindClique[CubeConnectedCycleGraph[n],Infinity,All],{n,3,10}])//Timing

Table[Piecewise[{{8,n==3}},3 (2^(n-1))n],{n,3,10}]

FindLinearRecurrence[Rest@seq]

Join[{1},LinearRecurrence[{4,-4},{3,12},20]]

seq=Join[{1},Table[3 (2^(n-1))n,{n,20}]]

FindGeneratingFunction[seq,x]

CoefficientList[Series[((1-x+4 (x^2))/(((-1+2 x))^2)),{x,0,20}],x]

seq=Join[{20},LinearRecurrence[{4,-4},{96,240},30]]

gf=(x^3) FindGeneratingFunction[seq,x]

Simplify[SeriesCoefficient[gf,{x,0,n}],n>2]

Table[If[n==3,20,3 (2^(n-1))n],{n,3,20}]

CoefficientList[Series[-((4 (-5-4 x+16 (x^2)))/(((-1+2 x))^2)),{x,0,20}],x]

Cycle

=== MaximalCliqueCount

Entity["Graph",{"Cycle",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Cycle",n},"MaximumCliqueCount"],{n,3,20}]

Empty

=== MaximalCliqueCount

Entity["Graph",{"Empty",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Empty",n},"MaximumCliqueCount"],{n,20}]

FibonacciCube

=== MaximalCliqueCount

A001629

seq=Table[GraphData[{"FibonacciCube",n},"MaximumCliqueCount"],{n,15}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

FindLinearRecurrence[seq]

Table[(2(n+1)Fibonacci[n]+n Fibonacci[n+1])/5,{n,20}]

FoldedCube

=== MaximalCliqueCount

A057711

seq=Table[GraphData[{"FoldedCube",n},"MaximumCliqueCount"],{n,2,10}]

Table[(n+2)2^n,{n,0,30}]

Join[{0,1},Table[n (2^(n-2)),{n,2,30}]]

FindLinearRecurrence[Table[n (2^(n-2)),{n,2,30}]]

Join[{0,1},LinearRecurrence[{4,-4},{2,6},20]]

FindGeneratingFunction[%,x]

CoefficientList[Series[((x (1-2 x+2 (x^2)))/(((1-2 x))^2)),{x,0,20}],x]

Gear

=== MaximalCliqueCount

seq=Table[GraphData[{"Gear",n},"MaximumCliqueCount"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["MaximumCliqueCount"]

Grid n×n

=== MaximalCliqueCount

Entity["Graph",{"Grid",{n,n}}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Grid",{n,n}},"MaximumCliqueCount"],{n,10}]

Table[Piecewise[{{1, n == 1}}, 2(-1 + n)n],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["MaximumCliqueCount"]

Grid n×n×n

=== MaximalCliqueCount

Entity["Graph",{"Grid",{n,n,n}}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Grid",{n,n,n}},"MaximumCliqueCount"],{n,10}]

seq=Table[Piecewise[{{1, n == 1}}, 3*(-1 + n)*n^2],{n,10}]

HalvedCube

A000079

seq=Table[GraphData[{"HalvedCube",n},"MaximumCliqueCount"],{n,10}]

FindSequenceFunction[Drop[seq,4],n-4]

Hanoi

A000244

seq=Table[GraphData[{"Hanoi",n},"MaximumCliqueCount"],{n,5}]

FindSequenceFunction[seq,n]

Helm

seq=Table[GraphData[{"Helm",n},"MaximumCliqueCount"],{n,3,20}]

FindSequenceFunction[Rest@seq,n-2]//Factor

Hypercube

=== MaximalCliqueCount

A001787

Entity["Graph",{"Hypercube",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Hypercube",n},"MaximumCliqueCount"],{n,0,10}]

Table[Piecewise[{{1, n == 0}}, 2^(-1 + n)n], {n,0,10}]

Join[{0},Table[n (2^(n-1)),{n,20}]]

seq=Table[n (2^(n-1)),{n,20}];

FindLinearRecurrence[seq]

Join[{0},LinearRecurrence[{4,-4},{1,4},20]]

FindGeneratingFunction[seq,x]

CoefficientList[Series[(x/(((-1+2 x))^2)),{x,0,20}],x]

Keller

A296100

seq=Table[GraphData[{"Keller",n},"MaximumCliqueCount"],{n,5}]

(seq=Table[Length@FindClique[KellerGraph[n],Length/@FindClique[KellerGraph[n]],All],{n,3}])//Timing

King n×n

=== MaximalCliqueCount

seq=Table[GraphData[{"King",{n,n}},"MaximumCliqueCount"],{n,10}]

Table[If[n==1,1,(((n-1))^2)],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["MaximumCliqueCount"]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Knight",{n,n}},"MaximumCliqueCount"],{n,10}]

Table[({{\[Piecewise], ({{1, n==1}, {4, n==2}, {4 (-2+n) (-1+n), True}})}}),{n,10}]

Ladder

=== MaximalCliqueCount

Entity["Graph",{"Ladder",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Ladder",n},"MaximumCliqueCount"],{n,20}]

Table[3n-2,{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"MaximumCliqueCount"],{n,20}]

MengerSponge

=== MaximalCliqueCount

A291066

seq=Table[GraphData[{"MengerSponge",n},"MaximumCliqueCount"],{n,3}]

(seq=Table[Length@FindClique[MengerSpongeGraph[n],Infinity,All],{n,4}])//Timing

MoebiusLadder

=== MaximalCliqueCount

Series[(1-x+x^2)/(1-2*x-x*y+x^2),{x,0,12}]

Entity["Graph",{"MoebiusLadder",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"MoebiusLadder",n},"MaximumCliqueCount"],{n,3,25}]

Mycielski

=== MaximalCliqueCount

Entity["Graph",{"Mycielski",n}]["EdgeCount"]

Entity["Graph",{"Mycielski",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Mycielski",n},"MaximumCliqueCount"],{n,11}]

Table[Piecewise[{{1,n==1}},(14 3^n-27 2^n+18)/36],{n,20}]

FindLinearRecurrence[Rest@seq]

Join[{0,0},LinearRecurrence[{6,-11,6},{1,5,20},20]]

seq=Table[If[n<2,0,(18-27 (2^n)+14 (3^n))/36],{n,0,10}]

FindGeneratingFunction[seq,x]

CoefficientList[Series[(((x^2) (1-x+(x^2)))/(1-6 x+11 (x^2)-6 (x^3))),{x,0,20}],x]

Odd

===MaximalCliqueCount

A033876

seq=Table[GraphData[{"Odd",n},"MaximumCliqueCount"],{n,7}]

Table[Piecewise[{{1,n==1||n==2}},n Binomial[2 n,n]/4],{n,20}]

Table[n Binomial[2 n,n]/4,{n,10}]

seq=Table[n Binomial[2 n,n]/4,{n,2,20}]

FindSequenceFunction[seq,n]//FullSimplify

Table[(((4^n) Gamma[(3/2)+n])/((Sqrt[π]) Gamma[1+n])),{n,20}]

FindLinearRecurrence[Table[n Binomial[2 n,n]/4,{n,2,100}]]//Head

FindGeneratingFunction[seq,x]//FullSimplify

CoefficientList[Series[-((1-(1/(Sqrt[1-4 x]))-4 x)/(2 x-8 (x^2))),{x,0,20}],x]

FullSimplify[x (-((1-(1/(Sqrt[1-4 x]))-4 x)/(2 x-8 (x^2))))]

Series[((((1-4 x))^(-3/2))-1)/2,{x,0,20}]

CoefficientList[Series[((((1-4 x))^(-3/2))-1)/(2x),{x,0,20}],x]

Pan

seq=Table[GraphData[{"Pan",n},"MaximumCliqueCount"],{n,3,20}]

Path

===MaximalCliqueCount

Entity["Graph",{"Path",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Path",n},"MaximumCliqueCount"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Prism",n},"MaximumCliqueCount"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"MaximumCliqueCount"],{n,10}]

FindSequenceFunction[Drop[seq,2],n-2]

(seq=Table[Length@FindClique[QueenGraph[n,n],Length/@FindClique[QueenGraph[n,n]],All],{n,18}])//Timing

coef=FindLinearRecurrence[Drop[seq,3]]

Take[Drop[seq,3],Length[coef]]

seq=Join[{1,1,10},LinearRecurrence[{2,1,-4,1,2,-1},{36,76,129,210,310,448},20]]

Join[{1,1},LinearRecurrence[{2,1,-4,1,2,-1},{-28,-9,10,36,76,129},{3,20}]]

Rook n×n

===MaximalCliqueCount

seq=Table[GraphData[{"Rook",{n,n}},"MaximumCliqueCount"],{n,10}]

RookComplement n×n

===MaximalCliqueCount

seq=Table[GraphData[{"RookComplement",{n,n}},"MaximumCliqueCount"],{n,10}]

FindSequenceFunction[seq,n]

SierpinskiCarpet

===MaximalCliqueCount

A271939

seq=Table[GraphData[{"SierpinskiCarpet",n},"MaximumCliqueCount"],{n,4}]

CoefficientList[Series[8/(1-11 x+24 x^2),{x,0,20}],x]

SierpinskiSieve

===MaximalCliqueCount

A003946

seq=Table[GraphData[{"SierpinskiSieve",n},"MaximumCliqueCount"],{n,5}]

(seq=Table[Length@FindClique[SierpinskiSieveGraph[n],∞,All],{n,10}])//Timing

FindSequenceFunction[Rest@seq,n-1]

seq=Table[4 (3^(-2+n)),{n,2,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{3},{4},20]

CoefficientList[Series[(1+x)/(1-3x),{x,0,20}],x]

SierpinskiTetrahedron

A000302

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"MaximumCliqueCount"],{n,6}]

FindSequenceFunction[seq,n]//FullSimplify

Star

===MaximalCliqueCount

Entity["Graph",{"Star",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Star",n},"MaximumCliqueCount"],{n,20}]

Sun

seq=Table[GraphData[{"Sun",n},"MaximumCliqueCount"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"MaximumCliqueCount"],{n,3,20}]

Tetrahedral

A000217

seq=Table[GraphData[{"Tetrahedral",n},"MaximumCliqueCount"],{n,6,10}]

(seq=Table[Length@FindClique[TetrahedralGraph[n],Length/@FindClique[TetrahedralGraph[n]],All],{n,6,15}])//Timing

FindSequenceFunction[Rest@seq,n-6]//Factor

Binomial[n,2]

TorusGrid n×n

===MaximalCliqueCount

seq=Table[GraphData[{"TorusGrid",{n,n}},"MaximumCliqueCount"],{n,3,10}]

FindSequenceFunction[Rest@seq,n-3]//Factor

Transposition

===MaximalCliqueCount

A001809

Entity["Graph",{"Transposition",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Transposition",n},"MaximumCliqueCount"],{n,6}]

FindSequenceFunction[seq,n]

Table[CoefficientList[n!*LaguerreL[n,x],x],{n,0,6}]//Column

Table[n!Coefficient[LaguerreL[n,x],x,2],{n,20}]

Coefficient[Table[n!LaguerreL[n,x],{n,20}],x,2]

Table[Piecewise[{{1, n == 1}}, (1/4)*(-1 + n)*n*n!],{n,20}]

Table[n!Binomial[n,2]/2,{n,0,20}]

seq=Table[ (1/4)*(-1 + n)*n*n!,{n,40}];

FindLinearRecurrence[seq]//Head

FindGeneratingFunction[seq,x]//Head

Triangular

===MaximalCliqueCount

A000125

seq=Table[GraphData[{"Triangular",n},"MaximumCliqueCount"],{n,2,20}]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n]

gf=(x^2)FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>1]

Table[Binomial[n,3]+n,{n,20}]

Table[Piecewise[{{1,n==2||n==3}},Binomial[n,3]+n],{n,2,20}]

TriangularGrid

===MaximalCliqueCount

seq=Table[GraphData[{"TriangularGrid",n},"MaximumCliqueCount"],{n,0,10}]

Web

seq=Table[GraphData[{"Web",n},"MaximumCliqueCount"],{n,3,20}]

Wheel

===MaximalCliqueCount

Entity["Graph",{"Wheel",n}]["MaximumCliqueCount"]

seq=Table[GraphData[{"Wheel",n},"MaximumCliqueCount"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"MaximumCliqueCount"],{n,2,10}]

(seq=Table[Length@FindClique[WhiteBishopGraph[n,n],Length/@FindClique[WhiteBishopGraph[n,n]],All],{n,2,22}])//Timing

Algorithms

<<MathWorld`Graphs`

"FindClique"

DeleteCases[
{#,GraphData[#,"MaximumCliques"],FindMaximumCliques[GraphData[#],Method->"FindClique"]}&/@GraphData[;;12],
{_,x_,x_}]//Timing

"IGraphM"

DeleteCases[
{#,GraphData[#,"MaximumCliques"],FindMaximumCliques[GraphData[#],Method->"IGraphM"]}&/@GraphData[;;12],
{_,x_,x_}]//Timing