Clique

Author

Eric W. Weisstein
June 10, 2019

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

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

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

Table

GraphDataCountTable["CliqueCount",{"AlternatingGroupGraph"->308599,"Andrasfai"->115067,"Antelope"->308600,"Antiprism"->017077,"Apollonian"->205248,"Barbell"->000079,"Bishop"->183156,"BlackBishop"->295909,"Book"->016897,"Bruhat"->139149,"Centipede"->008586,"CocktailParty"->000244,"Complete"->000079,"CompleteBipartite"->000290,{"CompleteTripartite",3}->000578,"CrossedPrism"->017281,"Crown"->002061,"CubeConnectedCycle"->295926,"Cycle"->308602,"DiagonalIntersection"->300524,"Dipyramid"->308603,"Empty"->000027,"FibonacciCube"->291916,"Fiveleaper"->308604,"FoldedCube"->295921,"Gear"->016873,{"Grid",2}->056105,{"Grid",3}->295907,"HalvedCube"->295922,"Hanoi"->295911,"Helm"->016933,"Hypercube"->132750,"Keller"->295902,"King"->295906,"Knight"->295905,"Ladder"->016897,"LadderRung"->016777,"MengerSponge"->292209,"MoebiusLadder"->016861,"Mycielski"->199109,"Odd"->295934,"Pan"->005408,"Path"->005843,"PathComplement"->000045,"PermutationStar"->139149,"Prism"->016861,"Queen"->295903,"Rook"->288958,"RookComplement"->002720,"SierpinskiCarpet"->295932,"SierpinskiSieve"->295933,"SierpinskiTetrahedron"->292537,"Star"->005843,"Sun"->295904,"Sunlet"->016813,"Tetrahedral"->289837,"TorusGrid"->056107,"Transposition"->308606,"Triangular"->290056,"TriangularGrid"->242658,"TriangularHoneycombAcuteKnight","TriangularHoneycombBishop","TriangularHoneycombObtuseKnight","TriangularHoneycombQueen","TriangularHoneycombRook","TriangularSnake","Web"->016993,"Wheel"->308607,"WhiteBishop"->295910}]

Parametrized families

AlternatingGroupGraph

A308599

seq=Table[GraphData[{"AlternatingGroupGraph",n},"CliqueCount"],{n,2,6}]

Do[Print[{n,CliquePolynomial[AlternatingGroupGraph[n],1]//Timing}],{n,2,7}]

Andrasfai

A115067

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

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//Factor

seq=Table[(3n+5)n/2,{n,0,20}]

LinearRecurrence[{3,-3,1},{0,4,11},20]

gf=x FindGeneratingFunction[seq,x]

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

Antelope n×n

A308600

seq=Table[GraphData[{"Antelope",{n,n}},"CliqueCount"],{n,15}]

Table[GraphData[{"Antelope",{n,n}},"Connected"],{n,15}]

FindSequenceFunction[Drop[seq,3],n-3]//Factor

Table[Piecewise[{{2,n==1},{5,n==2}},49-28 n+5 (n^2)],{n,50}]

Antiprism

A017077

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

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

FindLinearRecurrence[Table[8n+1,{n,20}]]

LinearRecurrence[{2,-1},{9,17},{0,20}]

Apollonian

A205248

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

FindSequenceFunction[seq,n]

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

4(3^Range[20]+1)

FindLinearRecurrence[seq]

LinearRecurrence[{4,-3},{16,40},20]

gf=x FindGeneratingFunction[seq,x]

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

Barbell

A000079

seq=Table[GraphData[{"Barbell",n},"CliqueCount"],{n,3,20}]

Bishop n×n

A183156

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

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

FullSimplify[Total[{
(1/12) (-25+(((-2))^(1+n))+(((-1))^n)+19 (2^(1+n))-6 n (4+n)), (* black *)
(1/12) (-23+(((-1))^(1+n))+(2^(1+n)) (17+(((-1))^n))-6 n (4+n)) (* white *)
}]]

FindLinearRecurrence[seq]

seq=LinearRecurrence[{5,-9,7,-2},{2,7,22,59},{0,20}]

FindGeneratingFunction[seq,x]

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

BlackBishop n×n

A295909

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

(seq=Table[Length@FindAllCliques[BlackBishopGraph[n,n]],{n,20}])//Timing

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{2,4,-10,1,8,-4},{2,4,14,30,82,160},40]

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

Table[((((-2))^(n+1))+(((-1))^n)+19 (2^(n+1))-6 n (n+4)-25)/12,{n,20}]

gf=x FindGeneratingFunction[seq,x]

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

Book

A016897

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

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

Bruhat

A139149

seq=Table[GraphData[{"Bruhat",n},"CliqueCount"],{n,6}]

FindSequenceFunction[seq,n]

seq=Table[(n!+2)/2,{n,2,20}]

FindSequenceFunction[seq,n]//FullSimplify

FindGeneratingFunction[seq,x]//Head//Timing

Centipede

A008586

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

FindSequenceFunction[seq,n]

CocktailParty

A000244

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

FindSequenceFunction[seq,n]

Complete

A000079

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

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

CompleteBipartite m×n

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

CompleteBipartite n×n

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

A000290

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

FindSequenceFunction[seq,n]//Factor

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

A000578

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

CrossedPrism

A017281

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

FindSequenceFunction[seq,n-1]//Factor

Table[10n+1,{n,0,20}]

10Range[0,20]+1

FindLinearRecurrence[seq]

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

FindGeneratingFunction[seq,x]

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

Crown

A002061

seq=Table[GraphData[{"Crown",n},"CliqueCount"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

CubeConnectedCycle

A295926

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

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

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

(seq=Table[Length@FindAllCliques[CubeConnectedCycleGraph[n]],{n,3,11}])//Timing

FindLinearRecurrence[Rest@seq]

seq=Join[{69},LinearRecurrence[{5,-8,4},{161,401,961},30]]

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

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

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

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

Cycle

A308602

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

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

Table[({{\[Piecewise], ({{8, n==3}, {1+2 n, True}})}}),{n,3,100}]

DiagonalIntersection

A300524

seq=Table[GraphData[{"DiagonalIntersection",n},"CliqueCount"],{n,3,14}]

Dipyramid

A308603

seq=Table[GraphData[{"Dipyramid",n},"CliqueCount"],{n,3,20}]

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

Table[Piecewise[{{24,n==3}},3 (1+2 n)],{n,3,50}]

Empty

A000027

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

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

FibonacciCube

A291916

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

LinearRecurrence[{3,-1,-3,1,1},{4,6,11,19,34},20]

Table[((25-19 Sqrt[5]) (1-Sqrt[5])^n+(1+Sqrt[5])^n (25+19 Sqrt[5]))/(25 2^(n+1))+n LucasL[n+1]/5+1,{n,20}]//Expand

Table[(n LucasL[n+1]+LucasL[n+4]-Fibonacci[n-3])/5+1,{n,20}]

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

Fiveleaper n×n

A308604

seq=Table[GraphData[{"Fiveleaper",{n,n}},"CliqueCount"],{n,10}]

Table[GraphData[{"Fiveleaper",{n,n}},"Connected"],{n,10}]

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

Join[{2,5,10,17},Table[49-38 n+7 (n^2),{n,5,50}]]

FoldedCube

A295921

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

(seq=Table[Length@FindAllCliques[FoldedCubeGraph[n]],{n,2,13}])//Timing

FindLinearRecurrence[Drop[seq,2]]

Join[{4,16},LinearRecurrence[{5,-8,4},{25,57,129},20]]

FindSequenceFunction[Drop[seq,2],n-3]//FullSimplify

Table[Piecewise[{{4,n==2},{16,n==3}},(2^(n-2)) (n+2)+1],{n,2,40}]

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

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

Gear

A016873

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

FindSequenceFunction[seq,n-2]//Factor

Table[5n+2,{n,0,20}]

seq=5Range[0,20]+2

FindLinearRecurrence[seq]

LinearRecurrence[{2,-1},{7,12},{0,20}]

gf=x FindGeneratingFunction[seq,x]

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

Grid m×n

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

Grid n×n

A056105

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

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

seq=Table[3n^2-2n+1,{n,50}]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

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

Grid k×m×n

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

Grid n×n×n

A295907

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

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

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

FindLinearRecurrence[seq]

LinearRecurrence[{4,-6,4,-1},{2,21,82,209},20]

gf=x FindGeneratingFunction[seq,x]

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

HalvedCube

A295922

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

(seq=Table[Length@FindAllCliques[HalvedCubeGraph[n]],{n,11}])//Timing

(seq=Table[Length@FindAllCliques[HalvedCubeGraph[n]],{n,12}])//Timing

FindSequenceFunction[seq,n]//FullSimplify

seq=Table[(24(2+(4^n))+(2^n) n ((n-9) n-16))/48,{n,30}]

coef=FindLinearRecurrence[seq]

Length[coef]

Take[seq,Length@coef]

LinearRecurrence[{13,-68,184,-272,208,-64},{2,4,16,81,393,1777},20]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((2-22 x+100 (x^2)-223 (x^3)+236 (x^4)-96 (x^5))/((((-1+2 x))^4) (1-5 x+4 (x^2)))),{x,0,20}],x]

Hanoi

A295911

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

(seq=Table[Length@FindAllCliques[HanoiGraph[n]],{n,7}])//Timing

FindSequenceFunction[seq,n]

Table[(17 3^n-3)/6,{n,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{4,-3},{8,25},40]

gf=x FindGeneratingFunction[seq,x]

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

Helm

A016933

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

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

Table[6n+2,{n,0,20}]

seq=6Range[0,20]+2

FindLinearRecurrence[seq]

LinearRecurrence[{2,-1},{8,14},{0,20}]

gf=x FindGeneratingFunction[seq,x]

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

Hypercube

A132750 (except for first term)

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

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

FindSequenceFunction[seq,n+1]//FullSimplify

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

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

Calculate

Keller

A295902

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

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

King n×n

A295906

Entity["Graph",{"King",{n,n}}]["CliqueCount"]

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

FindSequenceFunction[seq,n]//Factor

seq=Table[2(5n^2-8n+4),{n,50}]

FindLinearRecurrence[seq]

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

gf=x FindGeneratingFunction[seq,x]

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

Knight n×n

A295905

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

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

FindSequenceFunction[seq,n]

seq=Table[5n^2-12 n+9,{n,50}]

FindLinearRecurrence[seq]

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

gf=x FindGeneratingFunction[seq,x]

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

Ladder

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

A016897

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

Range[4,100,5]

seq=Table[5n+4,{n,20}]

FindLinearRecurrence[seq]

5Range[0,20]+4

LinearRecurrence[{2,-1},{9,14},{0,20}]

FindGeneratingFunction[%145,x]

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

LadderRung

A016777

Entity["Graph",{"LadderRung",n}]["CliqueCount"]

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

FindSequenceFunction[seq,n]

MengerSponge

A292209

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

Table[3 20^n-2 8^n+1,{n,20}]

LinearRecurrence[{29,-188,160},{45,1073,22977},20]

CoefficientList[Series[(-45+232 x-320 x^2)/(-1+29 x-188 x^2+160 x^3),{x,0,20}],x]

MoebiusLadder

A016861

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

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

FindSequenceFunction[seq,n-2]//Factor

FindLinearRecurrence[seq]

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

gf=FindGeneratingFunction[seq,x]

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

Mycielski

A199109

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

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

Table[(7 3^n+1)/2,{n,0,20}]

seq=(7 3^Range[0,20]+1)/2

FindLinearRecurrence[seq]

LinearRecurrence[{4,-3},{11,32},{0,20}]

FindGeneratingFunction[seq,x]

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

Odd

A295934

Entity["Graph",{"Odd",n}]["CliqueCount"]

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

(seq=Table[Length@FindAllCliques[MyOddGraph[n]],{n,7}])//Timing

(seq=Table[Length@FindAllCliques[MyOddGraph[n]],{n,8}])//Timing

Do[Print[{n,Length@FindAllCliques[MyOddGraph[n]]//Timing}],{n,10}]

seq={2,8,26,106,442,1849,7723,32176,133706};

Head/@Table[FindSequenceFunction[Drop[seq,k],n-k],{k,0,5}]//Union

Head/@Table[FindLinearRecurrence[Drop[seq,n]],{n,0,5}]//Union

FindGeneratingFunction[seq,x]

CoefficientList[Table[GraphData[{"Odd",n},"CliquePolynomial"][x],{n,7}],x]//Column

Table[Binomial[2n-1,n],{n,10}]

Table[{(2n-1)Binomial[2n-3,n-2],n Binomial[2 n,n]/4},{n,4}]

FullSimplify[Subtract@@{(2n-1)Binomial[2n-3,n-2],n Binomial[2 n,n]/4},n>1]

Table[(2n-1)Binomial[2n-3,n-2],{n,10}]

seq=Table[Binomial[2n-1,n]+(2n-1)Binomial[2n-3,n-2]+1,{n,50}]

FindLinearRecurrence[Drop[seq,2]]

gf=FullSimplify[x FindGeneratingFunction[seq,x]-x+x^2,x∈Reals]

FullSimplify[gf/x]

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

FindSequenceFunction[seq,n]

seq=Table[Piecewise[{{2,n==1},{8,n==2}},Binomial[2n-1,n]+(2n-1)Binomial[2n-3,n-2]+1],{n,50}]

FindLinearRecurrence[Table[1+Binomial[2n-1,n]+(2n-1)Binomial[2n-3,n-2],{n,3,200}]]//Head

Pan

A005408

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

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

Path

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

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

PermutationStar

A139149

seq=Table[GraphData[{"PermutationStar",n},"CliqueCount"],{n,6}]

Prism

A016861

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

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

Queen n×n

A295903

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

(seq=Table[Length@FindAllCliques[QueenGraph[n,n]],{n,15}])//Timing

(seq=Table[Length@FindAllCliques[QueenGraph[n,n]],{n,17}])//Timing

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

seq=LinearRecurrence[{6,-11,0,21,-18,-5,12,-4},{2,16,94,293,742,1642,3458,7087},30]

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

Table[3 (2^(n+1))+n ((((-1))^(n+1))+(2^(n+2))+n (9n-26)-2)/2-5,{n,20}]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((2+4 x+20 (x^2)-95 (x^3)-24 (x^4)+113 (x^5)+92 (x^6)-4 (x^7))/((((-1+x))^4) (((-1+x+2 (x^2)))^2))),{x,0,20}],x]

Rook n×n

A288958

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

LinearRecurrence[{7,-19,25,-16,4},{2,9,34,105,286},20]

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

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

RookComplement n×n

A002720

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

Table[n! LaguerreL[n,-1],{n,10}]

Table[(-1)^n HypergeometricU[-n,1,-1],{n,10}]

RecurrenceTable[{(n+1)^2 a[n]-2 (n+2) a[n+1]+a[n+2]==0,a[1]==2,a[2]==7},a,{n,10}]

SierpinskiCarpet

A295932

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

(seq=Table[Length@FindAllCliques[SierpinskiCarpetGraph[n]],{n,5}])//Timing

(seq=Table[Length@FindAllCliques[SierpinskiCarpetGraph[n]],{n,6}])//Timing

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

seq=Table[(13 (8^n)-8 (3^n)+5)/5,{n,22}]

FindLinearRecurrence[seq]

LinearRecurrence[{12,-35,24},{17,153,1289},20]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((-17+51 x-48 (x^2))/(-1+12 x-35 (x^2)+24 (x^3))),{x,0,20}],x]

SierpinskiSieve

A295933

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

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

FindSequenceFunction[Rest@seq,n-1]

Table[If[n==1,8,5(3+7 (3^(n-1)))/6],{n,20}]

FindLinearRecurrence[Rest@seq]

Join[{8},LinearRecurrence[{4,-3},{20,55},30]]

gf=x FindGeneratingFunction[seq,x]

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

SierpinskiTetrahedron

A292537

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

Table[Piecewise[{{16,n==1}},7 4^n/2+3],{n,20}]

Join[{16},LinearRecurrence[{5,-4},{59,227},20]]

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

Star

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

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

Sun

A295904

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

FindSequenceFunction[seq,n-2]//FullSimplify

seq=Table[(2^n)+4 n,{n,40}]

FindLinearRecurrence[seq]

LinearRecurrence[{4,-5,2},{6,12,20},20]

gf=x FindGeneratingFunction[seq,x]

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

Sunlet

A016813

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

FindSequenceFunction[seq,n-2]//FullSimplify

Table[Piecewise[{{14,n==3}},4n+1],{n,3,20}]

Table[4n+1,{n,0,20}]

4Range[0,20]+1

FindLinearRecurrence[%]

LinearRecurrence[{2,-1},{5,9},{0,20}]

FindGeneratingFunction[%172,x]

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

Tetrahedral

A289837

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

Table[(2^(n-2)-n+1) Binomial[n,2]+Binomial[n,3]+5 Binomial[n,4]+1,{n,20}]

LinearRecurrence[{11,-52,138,-225,231,-146,52,-8},{1,1,2,16,76,261,757,2003},20]

CoefficientList[Series[(1-10 x+43 x^2-92 x^3+91 x^4-25 x^5-5 x^6-8 x^7)/((-1+x)^5 (-1+2 x)^3),{x,0,20}],x]

TorusGrid n×n

A056107

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

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

Table[If[n==3,34,3(n^2)+1],{n,3,10}]

seq=1+3((Range[0,20])^2)

FindLinearRecurrence[seq]

Transposition

A308606

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

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

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n]

FindGeneratingFunction[seq,x]

Triangular

A290056

seq=Table[GraphData[{"Triangular",n},"CliqueCount"],{n,2,10}]

(seq=Table[Length@FindAllCliques[TriangularGraph[n]],{n,2,20}])//Timing

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//FullSimplify

Table[1+Binomial[n,2]+Binomial[n,3]+(2^(n-1)-n) n,{n,20}]

gf=x FindGeneratingFunction[seq,x]

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

TriangularGrid

A242658

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

FindSequenceFunction[seq,n+1]//Factor

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

FindLinearRecurrence[seq]

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

FindGeneratingFunction[seq,x]

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

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"CliqueCount"],{n,20}]

FindSequenceFunction[seq,n]

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

Table[10-9 n+3 (n^2),{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"CliqueCount"],{n,9}]

FindSequenceFunction[seq,n]//Factor

Table[(1/2) (-6+(2^(3+n))-5 n-(n^2)),{n,9}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"CliqueCount"],{n,20}]

FindSequenceFunction[seq,n]//Factor

FindSequenceFunction[Drop[seq,3],n-3]//Factor

gf=x FindGeneratingFunction[seq,x]

SeriesCoefficient[gf,{x,0,n}]//Factor

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"CliqueCount"],{n,10}]

FindSequenceFunction[seq,n]//Factor

gf=x FindGeneratingFunction[seq,x]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"CliqueCount"],{n,10}]

FindSequenceFunction[seq,n]//Factor

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"CliqueCount"],{n,1,19,2}]

FindSequenceFunction[seq,(n+1)/2]//Factor

A016789

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

Web

A016993

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

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

7Range[0,20]+1

Table[7n+1,{n,0,20}]

FindLinearRecurrence[Rest@seq]

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

gf=FindGeneratingFunction[seq,x]

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

Wheel

A308607

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

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

Table[If[n==4,16,2(2n-1)],{n,4,60}]

WhiteBishop n×n

A295910

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

(seq=Table[Length@FindAllCliques[WhiteBishopGraph[n,n]],{n,2,20}])//Timing

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{2,4,-10,1,8,-4},{4,9,30,61,160,301},40]

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

Table[((((-1))^(n+1))+(2^(n+1)) (17+(((-1))^n))-6 n (n+4)-23)/12,{n,20}]

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

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

Algorithm

?FindAllCliques

(Subscript[Q, 4])

(i1=FindAllCliques[GraphData["Q4"],Method->"FindClique"])//Length//Timing

(i2=FindAllCliques[GraphData["Q4"],Method->{"CompleteGraphQ","KSubsets"}])//Length//Timing

(i3=FindAllCliques[GraphData["Q4"],Method->{"CompleteGraphQ",All}])//Length//Timing

i1===i2===i3

(Subscript[Q, 5])

(i1=FindAllCliques[GraphData["Q5"],Method->"FindClique"])//Length//Timing

(i2=FindAllCliques[GraphData["Q5"],Method->{"CompleteGraphQ","KSubsets"}])//Length//Timing

(i3=FindAllCliques[GraphData["Q5"],Method->{"CompleteGraphQ",All}])//Length//Timing

i1===i2===i3

(Subscript[Q, 6])

FindAllCliques[GraphData["Q6"],FindClique[GraphData["Q6"],Infinity,All]]//Length//Timing

(i1=FindAllCliques[GraphData["Q6"],Method->"FindClique"])//Length//Timing

(i2=FindAllCliques[GraphData["Q6"],Method->{"CompleteGraphQ","KSubsets"}])//Length//Timing

(i3=FindAllCliques[GraphData["Q6"],Method->{"CompleteGraphQ",All}])//Length//Timing

i1===i2===i3