Clique Covering Number

Author

Eric W. Weisstein
December 8, 2023

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

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

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

Parametrized family table

GraphDataCountTable["CliqueCoveringNumber",{"Alkane"->005843,"Andrasfai"->032766,"Antelope"->286069,"Antiprism"->004523,"Book"->27,"Fiveleaper"->301758,"Tetrahedral"->002620}]

Parametrized families

<<MathWorld`Graphs`

Andrasfai

A032766

Inferred for n > 10:

seq=Table[GraphData[{"Andrasfai",n},"CliqueCoveringNumber"],{n,20}]

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

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

Antelope n×n

A286069

Inferred for n > 15:

seq=Table[GraphData[{"Antelope",{n,n}},"CliqueCoveringNumber"],{n,20}]

Do[Print[{n,CliqueCoveringNumber[AntelopeGraph[n,n]]//Timing}],{n,40}]

(seq=Table[CliqueCoveringNumber[AntelopeGraph[n,n]],{n,30}])//Timing

(seq=Table[CliqueCoveringNumber[AntelopeGraph[n,n],Method->{"Trick","LinearOptimization","MOSEK"}],{n,30}])//Timing

Table[CliqueCoveringNumber[AntelopeGraph[n,n]],{n,41,50}]

Table[CliqueCoveringNumber[AntelopeGraph[n,n]],{n,51,55}]

seq={1,4,9,16,21,24,25,36,48,60,72,84,92,98,113,132,153,168,185,200,221,242,265,288,313,338,365,392,421,450,481,512,545,578,613,648,685,722,761,800,841,882,925,968,1013,1058,1105,1152,1201,1250,1301,1352,1405,1458,1513};

Length[seq]

Table[ConnectedGraphQ[AntelopeGraph[n,n]],{n,20}]

Take[seq,19]

FindLinearRecurrence[Drop[seq,18]]//Head

FindLinearRecurrence[Drop[seq,19]]

Take[Drop[seq,19],4]

LinearRecurrence[{2,0,-2,1},{200,221,242,265},{-18,0}]

LinearRecurrence[{2,0,-2,1},{1,2,5,8},55]

Join[{1,4,9,16,21,24,25,36,48,60,72,84,92,98,113,132,153,168,185},LinearRecurrence[{2,0,-2,1},{1,2,5,8},{20,55}]]==seq

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

FindGeneratingFunction[Drop[seq,19],x]

Antiprism

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

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

Table[Floor[((2 (1+n))/3)],{n,3,25}]

Apollonian

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

FindSequenceFunction[seq,n]

Barbell

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

Bishop n×n

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

BlackBishop n×n

Inferred for n > 10:

seq=Table[GraphData[{"BlackBishop",{n,n}},"CliqueCoveringNumber"],{n,20}]

FindSequenceFunction[Rest@DeleteMissing@seq,n-1]

Table[Piecewise[{{1,n==1}},n-1],{n,20}]==seq

Book

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

Bruhat

A001710

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

Do[Print[{n,CliqueCoveringNumber[BruhatGraph[n]]//Timing}],{n,7}]

Numerator[Range[7]!/2]

Centipede

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

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

Crown

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

Cycle

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

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

Table[Piecewise[{{1,n==3}},Ceiling[n/2]],{n,3,20}]

DiagonalIntersection

A301745

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

l={{{"DiagonalIntersection",10},{0,71}}}

Table[RecognizeGraph[System`GraphComplement[PolygonDiagonalIntersectionGraph[n]]],{n,3,9}]

Do[Print[{n,CliqueCoveringNumber[PolygonDiagonalIntersectionGraph[n]]//Timing}],{n,3,16}]

seq={1,2,4,7,17,25,56,71,142,133,299,330,578,577};

FindSequenceFunction[DeleteMissing@seq,n-2]//Head

FindGeneratingFunction[DeleteMissing@seq,x]//Head

Dipyramidal

A004526

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

Ceiling[Range[3,20]/2]

Empty

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

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

FibonacciCube

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

Do[Print[{n,CliqueCoveringNumber[FibonacciCubeGraph[n]]//Timing}],{n,15}]

(seq=Table[CliqueCoveringNumber[FibonacciCubeGraph[n]],{n,15}])//Timing

seq={1,2,3,4,7,11,17,28,45,72,117,189,305,494,799};

Ceiling[Fibonacci[Range[3,17]]/2]

Fiveleaper n×n

A301758

seq=Table[GraphData[{"Fiveleaper",{n,n}},"CliqueCoveringNumber"],{n,20}]

Table[Length@FindAllMaximalIndependentVertexSets[GraphComplement@FiveleaperGraph[n,n]],{n,20}]//Timing

Do[Print[{n,CliqueCoveringNumber[FiveleaperGraph[n,n]]//Timing}],{n,20}]

seq=Table[CliqueCoveringNumber[FiveleaperGraph[n,n]],{n,30}]

Table[CliqueCoveringNumber[FiveleaperGraph[n,n]],{n,31,40}]

Table[ConnectedGraphQ[FiveleaperGraph[n,n]],{n,20}]

seq={1,4,9,16,21,22,25,32,41,50,61,72,85,98,113,128,145,162,181,200,221,242,265,288,313,338,365,392,421,450,481,512,545,578,613,648,685,722,761,800};

FullSimplify[FindSequenceFunction[Drop[seq,6],n-6]]

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

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

Join[{1,4,9,16,21,22},Table[(3+(((-1))^n)+2 n (n+2))/4,{n,6,20}]]

FindLinearRecurrence[Drop[seq,6]]

Position[seq,338]

Join[{1,4,9,16,21,22},LinearRecurrence[{2,0,-2,1},{25,32,41,50},20]]

x FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[((-1-2 x-(x^2)+4 (x^4)+6 (x^5)-4 (x^6)-8 (x^7)+4 (x^9))/((((-1+x))^3) (1+x))),{x,0,n}],n>0]

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

FoldedCube

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

Gear

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

Grid m×n

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

Grid n×n

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

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

Grid k×m×n

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

Grid n×n×n

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

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

HalvedCube

Cf. A000983

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

Table[Length@FindAllMaximalIndependentVertexSets[GraphComplement@GraphData[{"HalvedCube",n}]],{n,10}]

(seq1=Table[CliqueCoveringNumber[HalvedCubeGraph[n]],{n,6,15}])//Timing

(seq2=Table[CliqueCoveringNumber[HalvedCubeGraph[n],Method->{"Trick","LinearOptimization","MOSEK"}],{n,6,15}])//Timing

Hanoi

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

FindSequenceFunction[seq,n]

Helm

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

Hypercube

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

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

Keller

Possibly A022308

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

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

(seq1=Table[CliqueCoveringNumber[KellerGraph[n]],{n,6,15}])//Timing

(seq2=Table[CliqueCoveringNumber[KellerGraph[n],Method->{"Trick","LinearOptimization","MOSEK"}],{n,6,15}])//Timing

King n×n

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

Knight m×n

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

Knight n×n

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

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

Ladder

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

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

LadderRung

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

MengerSponge

A307691

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

Do[Print[{n,CliqueCoveringNumber[MengerSpongeGraph[n]]//Timing}],{n,4}]

MoebiusLadder

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

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

Mycielski

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

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

Odd

A301749

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

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

Table[GraphData[{"Odd",n},"MaximalIndependentVertexSetCount"],{n,7}]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

Pan

A004526

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

FindSequenceFunction[seq,n-2]//FullSimplify

Table[1+Floor[n/2],{n,3,20}]

Path

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

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

PathComplement

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

Prism

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

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

Queen n×n

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

Rook n×n

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

RookComplement n×n

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

SierpinskiCarpet

A013731(n+1)

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

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

Do[Print[{n,CliqueCoveringNumber[SierpinskiCarpetGraph[n]]//Timing}],{n,4}]

seq={4,32,256,2048,16384};

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

SierpinskiSieve

A307685

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

Do[Print[{n,CliqueCoveringNumber[SierpinskiSieveGraph[n]]//Timing}],{n,10}]

seq={1,3,6,17,48,143,426,1277};

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

SierpinskiTetrahedron

A307702 = A199209(n-2) for n>=3

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

Do[Print[{n,CliqueCoveringNumber[SierpinskiTetrahedronGraph[n]]//Timing}],{n,7}]

seq={1,4,11,41,161,641};

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

Table[10 (4^(n-3))+1,{n,3,6}]

Join[{1,4},Table[10 (4^(n-3))+1,{n,3,20}]]

Star

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

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

Sun

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

Sunlet

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

Tetrahedral

A002620

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

Table[Floor[(n-1)^2/4],{n,6,15}]

(seq1=Table[CliqueCoveringNumber[TetrahedralGraph[n]],{n,6,12}])//Timing

(seq2=Table[CliqueCoveringNumber[TetrahedralGraph[n],Method->{"Trick","LinearOptimization","MOSEK"}],{n,6,15}])//Timing

TorusGrid n×n

A000982

seq=Table[GraphData[{"TorusGrid",{n,n}},"CliqueCoveringNumber"],{n,3,20}]

(seq1=Table[CliqueCoveringNumber[TorusGridGraph[n,n]],{n,3,20}])//Timing

(seq2=Table[CliqueCoveringNumber[TorusGridGraph[n,n],Method->{"Trick","LinearOptimization","MOSEK"}],{n,3,20}])//Timing

seq1===seq2

FullSimplify[FindSequenceFunction[Rest@seq2,n-4],n∈Integers]//Factor

Table[Piecewise[{{3,n==3}},Ceiling[n^2/2]],{n,3,20}]==seq1

Transposition

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

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

Triangular

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

TriangularGrid

A301752

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

seq={1,3,4,6,8,10,13,15,19,22,26,31,35,41,46,52,58,64,71,77,85,92,100,109};

Do[Print[{n,Length@FindAllMaximalIndependentVertexSets[System`GraphComplement[TriangularGridGraph[n]]]//Timing}],{n,10}]

Do[Print[{n,Max@FindVertexColoring[System`GraphComplement[TriangularGridGraph[n]],Method->"Static"]//Timing}],{n,20}]

f1=FindSequenceFunction[seq,n]//FullSimplify[#,n∈Integers]&

Table[f1,{n,20}]

f2=FindSequenceFunction[Rest@seq,n-1]//FullSimplify[#,n∈Integers]&

Table[f2,{n,20}]

FullSimplify[f1-f2]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{2,0,-1,-2,2,1,0,-2,1},{1,3,4,6,8,10,13,15,19},20]

gf=x FindGeneratingFunction[seq,x]

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

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

FullSimplify[Series[f2,{n,∞,1}],n∈Integers]

TriangularHoneycombAcuteKnight

A287195

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

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[(((-1-2 x) x)/((((-1+x))^3) (((1+x+(x^2)))^2))),{x,0,n}],n∈Integers&&n>0]

TriangularHoneycombBishop

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

TriangularHoneycombKing

seq=Table[GraphData[{"TriangularHoneycombKing",n},"CliqueCoveringNumber"],{n,11}]

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

TriangularHoneycombObtuseKnight

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

FindSequenceFunction[seq,n]//Factor

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

Web

A007494

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

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

Wheel

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

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

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"CliqueCoveringNumber"],{n,2,20}]

Algorithms

ChromaticNumberFromPolynomial

Monitor[DeleteCases[{g=#,ChromaticNumberFromPolynomial[System`ChromaticPolynomial[System`GraphComplement@GraphData[#],x],x],GraphData[#,"CliqueCoveringNumber"]}&/@GraphData[;;10],{_,x_,x_}],g]//Timing

Monitor[DeleteCases[{g=#,ChromaticNumberFromPolynomial[System`ChromaticPolynomial[System`GraphComplement@GraphData[#],x],x],GraphData[#,"CliqueCoveringNumber"]}&/@GraphData[;;12],{_,x_,x_}],g]//Timing

VertexColoring via ILP

Monitor[If[(ccn1=GraphData[g=#,"CliqueCoveringNumber"])=!=(ccn2=CliqueCoveringNumber[GraphData[#],Method->"ComplementVertexColoring"]),Print[{#,ccn1,ccn2}]]&/@SortBy[GraphData[;;10],GraphData[#,"V"]&],g];//Timing

Monitor[If[(ccn1=GraphData[g=#,"CliqueCoveringNumber"])=!=(ccn2=CliqueCoveringNumber[GraphData[#],Method->"ComplementVertexColoring"]),Print[{#,ccn1,ccn2}]]&/@SortBy[GraphData[;;12],GraphData[#,"V"]&],g];//Timing

CliqueCoveringNumber[GraphData[{"RookComplement",{7,7}}],Method->"ComplementVertexColoring"]//Timing

ChromaticNumber via LinearProgramming

Monitor[If[(ccn1=GraphData[g=#,"CliqueCoveringNumber"])=!=(ccn2=CliqueCoveringNumber[GraphData[#]]),Print[{#,ccn1,ccn2}]]&/@SortBy[GraphData[;;10],GraphData[#,"V"]&],g];//Timing

Monitor[If[(ccn1=GraphData[g=#,"CliqueCoveringNumber"])=!=(ccn2=CliqueCoveringNumber[GraphData[#]]),Print[{#,ccn1,ccn2}]]&/@SortBy[GraphData[;;12],GraphData[#,"V"]&],g];//Timing

CliqueCoveringNumber[GraphData[{"RookComplement",{7,7}}]]//Timing

Disconnected

DeleteCases[Monitor[Function[g,{gn=g,GraphData[g,"CliqueCoveringNumber"],Total[GraphData[#,"CliqueCoveringNumber"]&/@GraphData[g,"ConnectedComponents","Name"]]}]/@GraphData[;;20],gn],{_,x_,x_}]//Timing

DeleteCases[{#,#2,Total[#3]}&@@@DeleteCases[Function[{gn,cc},{gn,GraphData[gn,"CliqueCoveringNumber"],GraphData[#,"CliqueCoveringNumber"]&/@cc}]@@@Select[{#,GraphData[#,"ConnectedComponents","Name"]}&/@GraphData["Disconnected"],AllTrue[#[[2]],DataPaclets`GraphDataDump`MyGraphQ]&],{_,_Missing,_?(!FreeQ[#,_Missing]&)}],{_,x_,x_}]

Checks

ChromaticNumber of GraphComplement

DeleteCases[{#,CliqueCoveringNumber[GraphData[#]],VertexChromaticNumber[GraphComplement[GraphData[#]]]}&/@GraphData[;;8],{_,x_,x_}]//Timing