Maximal Independent Vertex Set

Author

Eric W. Weisstein
February 7, 2024

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

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

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

Missing

Grid[Sort[{GraphData[#,"V"],#}&/@GraphData["MaximalIndependentVertexSetCount","Missing"]],Dividers->All,Alignment->{{Decimal,Left}}]

Counts

FullTally[l_List]:=Module[{t=Sort[Tally[l]],f,r},
If[(f=t[[All,1]])===(r=Range@@f[[{1,-1}]]),t,Sort[Join[t,{#,0}&/@Complement[r,f]]]]
]

(FullTally/@(values=Table[Length[FindAllMaximalIndependentVertexSets[#]]&/@Graphs[n],{n,8}]))//Column

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

(tallies=FullTally[#][[All,2]]&/@(values=Get/@FileNames["*.m"]))//Column

Flatten[tallies]

A000088

Total/@tallies

Length/@tallies

Not in OEIS:

Total/@values

Table

GraphDataCountTable["MaximalIndependentVertexSetCount",{"AlternatingGroupGraph","Andrasfai","Antelope"->321242,"Antiprism"->290593,"Apollonian"->289021,"Barbell"->005563,"Bishop"->146304,"BlackBishop"->290594,"Book"->000079,"Bruhat","Camel"->367457,"Centipede"->000045,"CocktailParty"->000027,"Complete"->000027,"CompleteBipartite"->007395,"CompleteTripartite"->010701,"CrossedPrism"->276225,"Crown","CubeConnectedCycle","Cycle"->001608,"DiagonalIntersection"->292356,"Dipyramid"->290612,"Empty"->000012,"FibonacciCube"->291742,"Fiveleaper"->321247,"FoldedCube"->301460,"Gear"->259967,"Giraffe"->367458,{"Grid",2}->197048,{"Grid",3},"HalvedCube"->290606,"Hanoi"->321249,"Helm"->000032,"Hypercube"->284707,"Keller"->290607,"King"->288956,"Knight"->289201,"Ladder"->118658,"LadderRung"->000079,"LucasCube"->367681,"MengerSponge","MoebiusLadder"->290608,"Mycielski"->290609,"Odd"->290610,"Pan"->084338,"Path"->000931,"PathComplement"->028310,"Pell"->367686,"PermutationStar","Prism"->007040,"Queen"->146303,"Rook"->000142,"RookComplement"->103517,"SierpinskiCarpet","SierpinskiSieve","SierpinskiTetrahedron","Star"->040000,"Sun"->000027,"Sunlet"->000032,"Tetrahedral"->290611,"TorusGrid"->321250,"Transposition","Triangular"->133221,"TriangularGrid"->197564,"TriangularHoneycombAcuteKnight"->290614,"TriangularHoneycombBishop"->290615,"TriangularHoneycombObtuseKnight"->290617,"TriangularHoneycombQueen"->289883,"TriangularHoneycombRook"->000142,"TriangularSnake"->071679,"Web"->287498,"Wheel"->290612,"WhiteBishop"->290613,"Zebra"->367089}]

Parametrized families

Counts are the same as MinimalVertexCover

<<MathWorld`Graphs`

Andrasfai

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Antelope n×n

A321242

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

Length@DeleteMissing@seq

Position[Table[GraphData[{"Antelope",{n,n}},"Connected"],{n,20}],False]//Flatten

FindLinearRecurrence[DeleteMissing@Drop[seq,7]]//Head//Timing

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

Antiprism

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

A290593

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

FindLinearRecurrence[seq]

LinearRecurrence[{1,1,0,1},{3,12,15,31},20]

FindSequenceFunction[Rest@seq,n-3]

FindSequenceFunction[{0,4,3,12,15,31,49,92,156,279,484,855,1495,2629,4608,8092,14195,24916,43719,76727},n]

Table[2(((-1))^n)+RootSum[-1+#-2 ((#)^2)+((#)^3)&,#^n&],{n,3,40}]

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

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

Apollonian

A289021

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

seq={4,5,15,845,403227665,64175114443109790962237345,264288160993294964501375691029638701718807009656135518176301450923295365341665};

FindSequenceFunction[seq,n]//Head//Timing

FindLinearRecurrence[seq]//Head//Timing

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

T(t0, t1, x) = {[t0^3+t1^3*x, t0*t1^2]}
p(n, x)={my(v=[x, 1]); for(i=2, n, v=T(v[1], v[2], x)); v[1]+3*v[2]*x}
a(n)=p(n, 1);

T[t0_,t1_,x_]:={t0^3+t1^3x,t0 t1^2}
p[n_,x_]:=Module[{v={x,1}},
Do[v=T[v[[1]],v[[2]],x],{n-1}];
v[[1]]+3v[[2]]x
]

Table[p[n,1],{n,6}]

NestList[{#[[1]]^3+#[[2]]^3,#[[1]]#[[2]]^2}&,{1,1},6]

{1,3}.#&/@NestList[Function[{t,u},{t^3+u^3,t u^2}]@@#&,{1,1},6]

Barbell

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

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

Bishop n×n

A146304

seq=Table[GraphData[{"Bishop",{n,n}},"MaximalIndependentVertexSetCount"],{n,20}]

FindLinearRecurrence[seq]

FindSequenceFunction[DeleteMissing@seq,n]

MM[sig_List,n_,k_,d_,x_]:=MM[sig,n,k,d,x]=If[n==0,Boole[k==0],If[k>0,k*x*MM[sig,n-1,k-1,d,x],0]+If[k<n&&sig[[n]]>d,(sig[[n]]-d)*x*MM[sig,n-1,k,d+1,x],0]+If[k+sig[[n]]-d<n,MM[sig,n-1,k+sig[[n]]-d,sig[[n]],x],0]];
Q[sig_List,x_]:=MM[sig,Length[sig],0,0,x];
Bishop[n_,white_]:=Table[n-i+If[white==1,1-Mod[i,2],Mod[i,2]],{i,1,n-If[white==1,Mod[n,2],1-Mod[n,2]]}]
a[n_]:=Q[Bishop[n,0],1]*Q[Bishop[n,1],1];
Table[a[n],{n,1,20}]

BlackBishop m×n

Table[GraphData[{"BlackBishop",{m,n}},"MaximalIndependentVertexSetCount"],{n,10},{m,n}]//Column

BlackBishop n×n

A290594

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

Do[Print[{n,Length@FindIndependentVertexSet[BlackBishopGraph[n,n],Infinity,All]//Timing}],{n,12}]

seq={1,2,5,8,30,88,378,1400,7128,31456,182640};

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

A146304

M[sig_List,n_,k_,d_,x_]:=M[sig,n,k,d,x]=If[n==0,Boole[k==0],If[k>0,k*x*M[sig,n-1,k-1,d,x],0]+If[k<n&&sig[[n]]>d,(sig[[n]]-d)*x*M[sig,n-1,k,d+1,x],0]+If[k+sig[[n]]-d<n,M[sig,n-1,k+sig[[n]]-d,sig[[n]],x],0]];
Q[sig_List,x_]:=M[sig,Length[sig],0,0,x];
Bishop[n_,white_]:=Table[n-i+If[white==1,1-Mod[i,2],Mod[i,2]],{i,1,n-If[white==1,Mod[n,2],1-Mod[n,2]]}]
a[n_]:=Q[Bishop[n,0],1]

Table[a[n],{n,20}]

Book

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

Camel n×n

A367457

seq=Table[GraphData[{"Camel",{n,n}},"MaximalIndependentVertexSetCount"],{n,20}]

DeleteMissing@seq//Length

Position[Table[GraphData[{"Camel",{n,n}},"Connected"],{n,20}],True]//Flatten

FindLinearRecurrence[Rest@DeleteMissing@seq]//Head//Timing

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

Centipede

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

Table[Fibonacci[n+2],{n,10}]

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

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

DeleteCases[%,{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

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

DeleteCases[%,{_,x_,x_}]

CompleteTripartite n×n×n

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

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"MaximalIndependentVertexSetCount"],{n,6}]

CrossedPrism

A276225

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

FindLinearRecurrence[DeleteMissing@seq]

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

Crown

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

CubeConnectedCycle

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

Cycle

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

A001608

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

DiagonalIntersection

A292356

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

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"MaximalIndependentVertexSetCount"],{n,7}]

Empty

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

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

FibonacciCube

A291742

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

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k],n]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

Table[Length@MaximalSets[FindAllIndependentVertexSets[FibonacciCubeGraph[n]]],{n,6}]//Timing

Table[Length@FindAllMaximalIndependentVertexSets[FibonacciCubeGraph[n]],{n,7}]//Timing

Fiveleaper n×n

A321247

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

Length@DeleteMissing@seq

Position[Table[GraphData[{"Fiveleaper",{n,n}},"Connected"],{n,20}],False]//Flatten

FindLinearRecurrence[DeleteMissing@Drop[seq,7]]//Head//Timing

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

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

Gear

A259967

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

FindLinearRecurrence[DeleteMissing@seq]

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

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

GeneralizedPetersen

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

Giraffe n×n

A367458

seq=Table[GraphData[{"Giraffe",{n,n}},"MaximalIndependentVertexSetCount"],{n,20}]

Length@DeleteMissing@seq

Position[Table[GraphData[{"Fiveleaper",{n,n}},"Connected"],{n,20}],False]//Flatten

FindLinearRecurrence[DeleteMissing@Drop[seq,7]]//Head//Timing

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

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

Grid 3×n

Entity["Graph",{"Grid",{3,n}}]["MaximalIndependentVertexSetCount"]

A197049

seq=Table[GraphData[{"Grid",Sort[{3,n}]},"MaximalIndependentVertexSetCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

Factor[2-((2 x (1+x) (2 (x^3)-(x^2)-x-2))/(1-x-(x^2)-3 (x^3)+(x^4)+(x^5)))]

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

FindLinearRecurrence[Rest@seq]

LinearRecurrence[{1,1,3,-1,-1},{2,4,10,18,38,78},20]

res=Refine[SeriesCoefficient[gf=2*x-2*x^2*(1+x)*(2*x^3-x^2-x-2)/(1-x-x^2-3*x^3+x^4+x^5),{x,0,n}],n>1]/2

terms=List@@res;

approx=RootApproximant[N[exact=terms/.n->0,200],5]

pos=approx[[All,-2]]

N[approx-exact,200]

f1=1+#1-3 ((#1)^2)-((#1)^3)-((#1)^4)+((#1)^5)&;
f2=64-2229 #1+31828 ((#1)^2)-115916 ((#1)^3)+77296 ((#1)^4)+77296 ((#1)^5)&;

2Table[Sum[((Root[f1,k])^n)Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

seq

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]]

Equal@@Last/@an

2RootSum[f1,Evaluate[((#)^n) #^Range[0,Length[pos]-1].an[[1,2]]]&]

Table[Piecewise[{{2,n==1}},-(1/4831)RootSum[1+#1-3 ((#1)^2)-((#1)^3)-((#1)^4)+((#1)^5)&,10635 ((#1)^n)-16668 ((#1)^(1+n))-2575 ((#1)^(2+n))-7840 ((#1)^(3+n))+5520 ((#1)^(4+n))&]],{n,20}]

Grid m×n

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

Block[{m,n},Sort[{{m,n}="Grid"/.GraphData[#,"NotationRules"],GraphData[#,"MaximalIndependentVertexSetCount"],XXX}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&]]]

Grid n×n

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

A197048

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

seq={1,2,10,42,358,4468,88056,2745186,134355866,10264692132,1234801357470,232966546265096,68939282741912248};

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[seq,n]//Head//Timing

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

Grid k×m×n

Grid n×n

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

Grid n×n×n

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

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

HalvedCube

A290606

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

Hanoi

A321249

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

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k],n]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

FindLinearRecurrence[Drop[seq,2]]

FindGeneratingFunction[seq,x]

Helm

A000032

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

Table[LucasL[n],{n,3,20}]

Hypercube

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

A284707

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

Keller

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

A290607

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

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

FindGeneratingFunction[seq,x]

King m×n

Table[data[[Binomial[i,2]+(1/2) (j-1) (2 i+j)+1]],{i,10},{j,If[i==10,8,i]}]//Column

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

King 2×n

A107383

seq=Table[GraphData[{"King",Sort[{2,n}]},"MaximalIndependentVertexSetCount"],{n,10}]

FindLinearRecurrence[DeleteMissing@seq]

LinearRecurrence[{0,2,2},{2,4,6},20]

gf=x FindGeneratingFunction[seq,x]

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

FindSequenceFunction[seq,n]//FullSimplify

f1=-2-2 #1+((#1)^3)&;
f2=-1-3 #1-19 ((#1)^2)+19 ((#1)^3)&;
pos=Range[3];

Table[Sum[((Root[f1,k])^n)Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]]

Equal@@Last/@an

RootSum[f1,Evaluate[((#)^(n+Range[Length[pos]]-1)).an[[1,2]]]&]

Table[RootSum[-2-2 #+((#)^3)&,5 ((#)^n)+8 ((#)^(n+1))+((#)^(n+2))&]/19,{n,20}]

King n×n

A288956

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Knight m×n

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

Block[{m,n},Sort[{{m,n}="Knight"/.GraphData[#,"NotationRules"],GraphData[#,"MaximalIndependentVertexSetCount"],XXX}&/@GraphData["Knight"]]]

DeleteCases[%,{_,x_,x_}]

Knight n×n

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

A289201

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

Ladder

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

A118658(n-1)

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

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

Table[Fibonacci[n-1]+LucasL[n-1],{n,20}]

Table[Fibonacci[n-2]+LucasL[n-2],{n,0,20}]

Table[2Fibonacci[n-1],{n,0,20}]

2Fibonacci[Range[0,20]-1]

Table[LucasL[n]-Fibonacci[n],{n,0,20}]

Subtract@@@(Through[{LucasL,Fibonacci}[#]]&/@Range[0,20])

Through[{LucasL,Fibonacci}[#]]&/@Range[0,20]

Subtract@@@(Through[{LucasL,Fibonacci}[#]]&/@Range[0,20])

gf=x FindGeneratingFunction[%,x]//Factor

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

LadderRung

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

FindSequenceFunction[DeleteMissing@seq,n]

LucasCube

A367681

seq=Table[GraphData[{"LucasCube",n},"MaximalIndependentVertexSetCount"],{n,15}]

Do[Print[{gn={"LucasCube",n},IGraphM`IGMaximalCliquesCount[GraphComplement@GraphData[gn]]//Timing}],{n,10}]

MoebiusLadder

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

A290608

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

FindSequenceFunction[seq,n-2]//FullSimplify

Table[LucasL[n]-2 Cos[((2 n π)/3)],{n,3,40}]

%==seq

coef=FindLinearRecurrence[DeleteMissing@seq]

LinearRecurrence[{0,1,2,1},{2,8,12,16},20]

gf=x FindGeneratingFunction[seq,x]

Series[gf,{x,0,20}]

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

Mycielski

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

A290609

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

FindLinearRecurrence[DeleteMissing@seq]//Head//Timing

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

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

Do[Print[{gn={"Mycielski",n},IGraphM`IGMaximalCliquesCount[GraphComplement@GraphData[gn]]//Timing}],{n,8}]

Odd

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

A290610

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

FindSequenceFunction[DeleteMissing@seq,n]

Do[
Print[{{"Odd",n},Length@FindIndependentVertexSet[GraphData[{"Odd",n}],Infinity,All]//Timing}],
{n,5}]

Do[
Print[{{"Odd",n},IGraphM`IGMaximalCliquesCount[GraphComplement@GraphData[{"Odd",n}]]//Timing}],
{n,5}]

Pan

A084338

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

FindLinearRecurrence[DeleteMissing@seq]

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

LinearRecurrence[{0,1,1},{3,3,5},20]

FindSequenceFunction[seq,n]

f1=-1-#1+((#1)^3)&;
f2=-5+27 #1-46 ((#1)^2)+23 ((#1)^3)&;
pos={1,3,2};

Table[Sum[((Root[f1,k])^(n-2))Root[f2,pos[[k]]],{k,Length[pos]}],{n,3,10}]//N//Chop

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]]

Equal@@Last/@an

an[[1,2]]

RootSum[f1,Evaluate[((#)^(n+Range[Length[pos]]-1)).an[[1,2]]]&]

Table[RootSum[-1-#+((#)^3)&,12 ((#)^n)+4 ((#)^(n+1))+5 ((#)^(n+2))&]/23,{n,20}]

gf=x FindGeneratingFunction[LinearRecurrence[{0,1,1},{1,2,3},20],x]

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

Path

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

A000931: Padovan numbers

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

LinearRecurrence[{0,1,1},{1,2,2},20]

FindSequenceFunction[seq,n]

f1=-1-#1+((#1)^3)&;
f2=-1+2 #1-23 ((#1)^2)+23 ((#1)^3)&;

pos={1,2,3};

Table[Sum[((Root[f1,k])^n)Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]]

Equal@@Last/@an

RootSum[f1,Evaluate[((#)^n) #^Range[0,Length[pos]-1].an[[1,2]]]&]

Table[RootSum[-1-#1+((#1)^3)&,7 ((#1)^n)+10 ((#1)^(n+1))+((#1)^(n+2))&]/23,{n,20}]

Pell

A367686

seq=Table[GraphData[{"Pell",n},"MaximalIndependentVertexSetCount"],{n,9}]

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

Do[Print[{gn={"Pell",n},IGraphM`IGMaximalCliquesCount[GraphComplement@GraphData[gn]]//Timing}],{n,5}]

Prism

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

A007040

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

FindLinearRecurrence[seq]

LinearRecurrence[{0,1,2,1},{2,6,6,10},20]

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

Table[((((1/2) (1-(Sqrt[5]))))^n)+((((1/2) (1+(Sqrt[5]))))^n)+2 Cos[((2 n π)/3)],{n,3,25}]//FullSimplify

FullSimplify[n Sum[Binomial[2k,n-2k]/k,{k,n}]]

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

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

Table[((((1/2) (1-(Sqrt[5]))))^n)+((((1/2) (1+(Sqrt[5]))))^n),{n,10}]//FullSimplify

Table[LucasL[n]+2 Cos[((2 n π)/3)],{n,3,25}]

Queen n×n

A146303

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

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

seq={1,4,9,18,58,348,1862,10188,57600,376692,2640422,19469324,151978440,1258451524,10963084588,10008760018};

FindLinearRecurrence[seq]

FindLinearRecurrence[Rest@seq]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

gf=x FindGeneratingFunction[seq,x]

Rook n×n

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

FindSequenceFunction[seq,n]

RookComplement  n×n

A103517

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

FindSequenceFunction[Rest@seq,n-1]

seq=Join[{1},2Range[2,20]]

FindLinearRecurrence[Rest@seq]

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

x FindGeneratingFunction[seq,x]

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

StackedBook n×n

A321248

seq=Table[GraphData[{"StackedBook",{n,n}},"MaximalIndependentVertexSetCount"],{n,10}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

Star

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

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

Sun

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

FindSequenceFunction[seq,n-2]

Sunlet

A000032

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

FindSequenceFunction[seq,n-2]

Table[Fibonacci[2n]/Fibonacci[n],{n,3,20}]

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

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

Table[LucasL[n],{n,3,20}]

Tetrahedral

A290611

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

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

FindLinearRecurrence[DeleteMissing@seq]//Head//Timing

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

TorusGrid n×n

A321250

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

Transposition

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

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

Trapezohedron

A367644

Entity["Graph",{"Trapezohedron",n}]["MaximalIndependentVertexSetCount"]

seq=Table[GraphData[{"Trapezohedron",n},"MaximalIndependentVertexSetCount"],{n,3,20}]

A001608(2n) + 1 == Perrin(2n) + 1

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

A109377(n) + 1

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

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

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

InputForm[%]

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

InputForm[%]

f2=-1-3*#1-2*#1^2+#1^3&;
f1=-1+#1-2*#1^2+#1^3&;
pos={1,2,3};

an=ToNumberField[Root[f2,#],Root[f1,pos[[#]]]]&/@Range[3]

coeffs=an[[All,-1]]

SameQ@@coeffs

RootSum[f1,Evaluate[((#)^(n+Range[Length[pos]]-1)).an[[1,2]]]&]

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

FindLinearRecurrence[seq]

seq=LinearRecurrence[{3,-3,2,-1},{3,3,6,11},36]

ToString[seq]//StringLength

gf=x FindGeneratingFunction[seq,x]

StringReplace[ToString[gf,InputForm]," "->""]

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

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

Table[1+((NumericalApproximation[Root, (RowDefault["1.75", FEExpressionsNumericalApproximationElider]), Root[-1+#1-2 ((#1)^2)+((#1)^3)&,1], ])^n)+((NumericalApproximation[Root, (RowDefault["0.123", FEExpressionsNumericalApproximationElider])-(RowDefault["0.745", FEExpressionsNumericalApproximationElider]) I, Root[-1+#1-2 ((#1)^2)+((#1)^3)&,2], ])^n)+((NumericalApproximation[Root, (RowDefault["0.123", FEExpressionsNumericalApproximationElider])+(RowDefault["0.745", FEExpressionsNumericalApproximationElider]) I, Root[-1+#1-2 ((#1)^2)+((#1)^3)&,3], ])^n)]

Do[Print[{{"Trapezohedron",n},Length@Select[FindIndependentVertexSet[g=TrapezohedralGraph[n],Infinity,All],DominatingSetQ[g,#]&]//Timing}],{n,3,20}]

Triangular

A001147

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

FindSequenceFunction[DeleteMissing@seq,n-1]

Table[Piecewise[{{(n-1)!!,Mod[n,2]==0},{n!!,Mod[n,2]==1}}],{n,2,20}]

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

TriangularGrid

A197564

seq=Table[GraphData[{"TriangularGrid",n},"MaximalIndependentVertexSetCount"],{n,0,20}]

Length@DeleteMissing@seq-1

FindLinearRecurrence[DeleteMissing@seq]//Head//Timing

FindLinearRecurrence[Rest@DeleteMissing@seq]//Head//Timing

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

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

TriangularHoneycombAcuteKnight

A290614

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

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

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

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,4}]

TriangularHoneycombBishop

A290615

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"MaximalIndependentVertexSetCount"],{n,20}]

Table[Sum[k!StirlingS2[m,k]StirlingS2[n+1-m,k+1],{m,0,n},{k,0,Min[m,n-m]}],{n,20}]

Length@DeleteMissing@seq

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

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

FindLinearRecurrence[DeleteMissing@seq]//Head//Timing

TriangularHoneycombObtuseKnight

A290617

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

Length@DeleteMissing@seq

FindLinearRecurrence[DeleteMissing@seq]//Head//Timing

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

FindSequenceFunction[Drop[DeleteMissing@seq,4],n]//Head//Timing

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

Do[Print[{gn={"TriangularHoneycombObtuseKnight",n},IGraphM`IGMaximalCliquesCount[GraphComplement@GraphData[gn]]//Timing}],{n,20}]

Get["IGraphM`"]

IGVersion[]

IGraphM`Developer`GetInfo[]

IGraphM`IGMaximalCliquesCount[GraphComplement@GraphData[{"TriangularHoneycombObtuseKnight",15}]]//Timing//AbsoluteTiming

Emailed Szabolcs on Nov 28, 2023

TriangularHoneycombQueen

A289883

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"MaximalIndependentVertexSetCount"],{n,20}]

Length@DeleteMissing@seq

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

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

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"MaximalIndependentVertexSetCount"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]

Web

A287498

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

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n-2]

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

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

Table[RootSum[-1-3 #-2 ((#)^2)+((#)^4)&,#^n&],{n,30}]

LinearRecurrence[{0,2,3,1},{0,4,9,12},20]

Wheel

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

A290612

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

FindLinearRecurrence[seq]

LinearRecurrence[{1,1,0,-1},{4,3,6,6,8},50]

FindSequenceFunction[seq,n-3]

Table[1+((Root[-1-#1+((#1)^3)&,1])^(-3+n)) Root[-1+#1-2 ((#1)^2)+((#1)^3)&,1]+((Root[-1-#1+((#1)^3)&,3])^(-3+n)) Root[-1+#1-2 ((#1)^2)+((#1)^3)&,2]+((Root[-1-#1+((#1)^3)&,2])^(-3+n)) Root[-1+#1-2 ((#1)^2)+((#1)^3)&,3],{n,3}]//FullSimplify

FindSequenceFunction[{4,1,3,4,3,6,6,8,11,13,18,23,30,40,52,69,91,120,159,210},n]//FullSimplify

Table[1+((Root[-1-#1+((#1)^3)&,1])^n) Root[-1+((#1)^2)+((#1)^3)&,1]+((Root[-1-#1+((#1)^3)&,3])^n) Root[-1+((#1)^2)+((#1)^3)&,2]+((Root[-1-#1+((#1)^3)&,2])^n) Root[-1+((#1)^2)+((#1)^3)&,3],{n,4,20}]//FullSimplify

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

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

Table[1+RootSum[-1-#+((#)^3)&,#^(n-1)&],{n,4,20}]

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

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

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

WhiteBishop n×n

A290613

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

Do[Print[{n,Length@FindIndependentVertexSet[WhiteBishopGraph[n,n],Infinity,All]//Timing}],{n,12}]

A146304

M[sig_List,n_,k_,d_,x_]:=M[sig,n,k,d,x]=If[n==0,Boole[k==0],If[k>0,k*x*M[sig,n-1,k-1,d,x],0]+If[k<n&&sig[[n]]>d,(sig[[n]]-d)*x*M[sig,n-1,k,d+1,x],0]+If[k+sig[[n]]-d<n,M[sig,n-1,k+sig[[n]]-d,sig[[n]],x],0]];
Q[sig_List,x_]:=M[sig,Length[sig],0,0,x];
Bishop[n_,white_]:=Table[n-i+If[white==1,1-Mod[i,2],Mod[i,2]],{i,1,n-If[white==1,Mod[n,2],1-Mod[n,2]]}]
a[n_]:=Q[Bishop[n,1],1];

Table[a[n],{n,1,20}]

Zebra n×n

A367089

seq=Table[GraphData[{"Zebra",{n,n}},"MaximalIndependentVertexSetCount"],{n,20}]

Length@DeleteMissing@seq

FindLinearRecurrence[Rest@DeleteMissing@seq]//Head//Timing

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

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

Algorithms

Smallest

FindSmallestMaximalIndependentVertexSet[g_Graph?ConnectedGraphQ]:=
Sort[Sort/@FindIndependentVertexSet[g,{LowerIndependenceNumber[g]},All]][[1]]

FindSmallestMaximalIndependentVertexSet[g_Graph]:=Sort[Flatten[FindSmallestMaximalIndependentVertexSet/@ConnectedGraphComponents[g]]]

DeleteCases[Monitor[{g=#,FindSmallestMaximalIndependentVertexSet[GraphData[#]],GraphData[#,"MaximalIndependentVertexSets"]/.{Missing[_,l_]:>l,l_List:>First[l]}}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{
g=#,
sets=GraphData[#,"MaximalIndependentVertexSets"],
sets/.{Missing[_,l_]:>l,l_List:>First[l]},
FindSmallestMaximalIndependentVertexSet[GraphData[#],"LowerIndependenceNumber"->GraphData[#,"LowerIndependenceNumber"]]
}&/@GraphData[;;30],g],{__,x_,x_}]//Timing

"FindIndependentVertexSet"

DeleteCases[
Monitor[
{
gn=#,
MaximalIndependencePolynomial[GraphData[#],x,Method->"FindIndependentVertexSet"],
GraphData[#,"MaximalIndependencePolynomial"]/.f_Function:>f[x]
}&/@GraphData[;;10],
gn],
{_,x_,x_}]//AbsoluteTiming

"FindIndependentVertexSetIncremental"

DeleteCases[
Monitor[
{
gn=#,
MaximalIndependencePolynomial[GraphData[#],x,Method->"FindIndependentVertexSetIncremental"],
GraphData[#,"MaximalIndependencePolynomial"]/.f_Function:>f[x]
}&/@GraphData[;;10],
gn],
{_,x_,x_}]//AbsoluteTiming

IGraphM

DeleteCases[
Monitor[
{
gn=#,
MaximalIndependencePolynomial[GraphData[#],x,Method->"IGraphM"],
GraphData[#,"MaximalIndependencePolynomial"]/.f_Function:>f[x]
}&/@GraphData[;;10],
gn],
{_,x_,x_}]//AbsoluteTiming

IGraphMIncremental

DeleteCases[
Monitor[
{
gn=#,
MaximalIndependencePolynomial[GraphData[#],x,Method->"IGraphMIncremental"],
GraphData[#,"MaximalIndependencePolynomial"]/.f_Function:>f[x]
}&/@GraphData[;;10],
gn],
{_,x_,x_}]//AbsoluteTiming