Clique Number

Author

Eric W. Weisstein
February 9, 2024

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

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

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

Counts

Tally[Sort[#]]&/@(values=Table[CliqueNumber/@Graphs[n],{n,7}])//Column

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Table[CliqueNumber/@Graphs[n],{n,7}]))//Column

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/CliqueNumber"]

(tallies=Tally[Sort[#]][[All,2]]&/@(values=Get/@FileNames[]))//Column

A263341

Flatten[tallies]

A000088

Total/@tallies

Not in OEIS:

Total/@values

Relationships

IndependenceNumber of GraphComplement

DeleteCases[Monitor[{gn=#,CliqueNumber[GraphData[#]],IndependenceNumber[GraphComplement[GraphData[#]]]}&/@GraphData[;;10],gn],
{_,x_,x_}]//Timing

Parametrized family table

GraphDataCountTable["CliqueNumber"]

Parametrized families

Andrasfai

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

Antelope n×n

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

Antiprism

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

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

FindLinearRecurrence[Rest@seq]

seq=LinearRecurrence[{2,-1,1},{10,17,29},20]

RootSum[-1+#1-2 ((#1)^2)+((#1)^3)&,((#1)^(Range[0,20]))&]

gf=x FindGeneratingFunction[seq,x]

Apollonian

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

Barbell

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

Bishop n×n

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

BlackBishop n×n

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

Book

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

Bruhat

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

Centipede

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

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

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

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

Block[{k,m,n},Sort[{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],GraphData[#,"CliqueNumber"],XXX}&/@GraphData["CompleteTripartite"]]]

CompleteTripartite n×n×n

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

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

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

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

Cycle

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

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

DiagonalIntersection

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

Dipyramid

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

Empty

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

seq=Table[GraphData[{"Empty",n},"CliqueNumber"],{n,30}]

FibonacciCube

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

Fiveleaper n×n

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

FoldedCube

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

Gear

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

GeneralizedPetersen

Sort[{"GeneralizedPetersen"/.GraphData[#,"NotationRules"],GraphData[#,"CliqueNumber"]}&/@GraphData["GeneralizedPetersen"]]

Grid m×n

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

DeleteCases[Block[{m,n},Sort[{{m,n}="Grid"/.GraphData[#,"NotationRules"],GraphData[#,"CliqueNumber"],Piecewise[{{1,m==n==1}},2]}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&]]],{_,x_,x_}]

Grid n×n

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

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

seq={0,1,5,24,229,3436,65772,1743247,78586742,7234839185,1330059590925,421587920205546,212201572752086670,170288846375423693683,227570453486998336648738,527014715702923506908210573,2140337449056844246626590305042,1505530981318023673326716837253887};

FindLinearRecurrence[DeleteMissing@Drop[seq,3]]//Head

FindSequenceFunction[DeleteMissing@Rest@seq,n-1]//Head//Timing

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

Grid k×m×n

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

DeleteCases[Block[{m,n},Sort[{{k,m,n}="Grid"/.GraphData[#,"NotationRules"],GraphData[#,"CliqueNumber"],Piecewise[{{1,k==m==n==1}},2]}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==3&]]],{_,x_,x_}]

Grid n×n×n

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

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

HalvedCube

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

Hanoi

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

Helm

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

Hypercube

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

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

Keller

Entity["Graph",{"Keller",n}]["CliqueNumber"]

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

King m×n

Table[GraphData[{"King",{m,n}},"CliqueNumber"],{n,10},{m,n}]//Column

King n×n

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

Knight m×n

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

DeleteCases[Block[{m,n},Sort[{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"CliqueNumber"],Piecewise[{{1, Min[m, n] == 1 || m == n == 2}}, 2]}&/@GraphData["Knight"]]],{_,x_,x_}]

Knight n×n

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

seq=Table[GraphData[{"Knight",{n,n}},"CliqueNumber"],{n,20}]

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

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

Path

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

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

PathComplement

seq=Table[GraphData[{"PathComplement",n},"CliqueNumber"],{n,20}]

PermutationStar

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

Prism

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

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

Queen n×n

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

Rook n×n

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

RookComplement n×n

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

SierpinskiCarpet

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

SierpinskiSieve

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

SierpinskiTetrahedron

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

Star

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

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

Sun

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

Sunlet

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

Tetrahedral

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

TorusGrid n×n

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

Transposition

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

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

Triangular

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

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

Web

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

Wheel

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

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

WhiteBishop n×n

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

Examples

CliqueNumber[CompleteGraph[#]]&/@Range[6]

CliqueNumber[Cycle[#]]&/@Range[2,20]//Timing

CliqueNumber[Wheel[#]]&/@Range[3,20]//Timing

CliqueNumber[Star[#]]&/@Range[2,20]//Timing

graphs=Sort[{"PetersenGraph","OctahedralGraph","CubicalGraph","TetrahedralGraph","DodecahedralGraph","IcosahedralGraph","CoxeterGraph","FolkmanGraph","FruchtGraph","GrotztschGraph","HerschelGraph","MoebiusKantorGraph","PappusGraph","DesarguesGraph","DyckGraph","HeawoodGraph"}];

{#,CliqueNumber[ToExpression[#]]}&/@graphs//TableForm