Independent Vertex Set

Author

Eric W. Weisstein
December 25, 2023

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

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

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

Directed graphs

And independent edge set is a subset of the edges such that no two edges in the subset share a vertex.

Bidirected

g1=System`Graph[Range[3],{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1,2\[DirectedEdge]1,3\[DirectedEdge]2,1\[DirectedEdge]3},VertexLabels->"Name"]

Select[Subsets[VertexList[g1]],IndependentVertexSetQ[g1,#]&]

Length[%]

FindAllIndependentVertexSets[g1]

Cyclicly directed

g2=System`Graph[Range[3],{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1},VertexLabels->"Name"]

Select[Subsets[VertexList[g2]],IndependentVertexSetQ[g2,#]&]

FindAllIndependentVertexSets[g2]

Oppositely directed

g3=System`Graph[Range[3],{1\[DirectedEdge]2,2\[DirectedEdge]3,1\[DirectedEdge]3},VertexLabels->"Name"]

Select[Subsets[VertexList[g3]],IndependentVertexSetQ[g3,#]&]

FindAllIndependentVertexSets[g3]

Undirected

g4=UndirectedGraph[g,VertexLabels->"Name"]

Select[Subsets[VertexList[g4]],IndependentVertexSetQ[g4,#]&]

Algorithm comparisons

?FindAllIndependentVertexSets

(Subscript[Q, 4])

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

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

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

i1===i2===i3

(Subscript[Q, 5])

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

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

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

i1===i2===i3

Bugs

Table[FindIndependentVertexSet[GraphData[{"Hypercube",n}],Infinity,All]//Length,{n,4}]

...wrong...

FindIndependentVertexSet[GraphData[{"Hypercube",2}],{2},All]

i1=FindIndependentVertexSet[GraphData[{"Hypercube",2}],Infinity,All]

...wrong...

IndependentVertexSetQ[GraphData["Q2"],#]&/@i1

Table[AllIndependentVertexSets[GraphData[{"Hypercube",n}]]//Length,{n,0,4}]

AllIndependentVertexSets[GraphData[{"Hypercube",0}]]

IndependentVertexSetQ[GraphData["Q0"],#]&/@%

i2=AllIndependentVertexSets[GraphData[{"Hypercube",2}]]

FindAllVertexCovers[GraphData["Q2"]]

Sort[Complement[Range[4],#]&/@i2]

IndependentVertexSetQ[GraphData["Q2"],#]&/@i2

Counts table

GraphDataCountTable["IndependentVertexSetCount",{"Alkane"->228602,"Andrasfai"->288038,"Antelope"->286039,"Antiprism"->286910,"Apollonian"->289021,"Barbell"->005563,"Bishop"->201862,"BlackBishop"->216332,"Book"->085279,"Camel"->366513,"Centipede"->028859,"CocktailParty"->016777,"Complete"->000027,"CompleteBipartite"->000225,"CompleteTripartite"->033484,"CrossedPrism"->287327,"Crown"->083706,"CubeConnectedCycle"->292701,"Cycle"->000032,"CycleComplement"->308602,"DiagonalIntersection"->291948,"Dipyramid"->366506,"DorogovtsevGoltsevMendes"->368456,"DoubleCone"->366508,"Empty"->000079,"FibonacciCube"->291936,"Fiveleaper"->293150,"Flower"->366516,"FoldedCube"->290888,"Gear"->287350,"Giraffe"->366514,"Goldberg"->366515,"Grid"->006506,"HalvedCube"->288943,"Hanoi"->288490,"Helm"->287594,"Hypercube"->027624,"Keller"->284854,"King"->063443,"Knight"->141243,"Ladder"->001333,"LadderRung"->000244,"LucasCube"->366505,"MiddleLayer"->366518,"MoebiusLadder"->182143,"Mycielski"->292710,"Odd"->292711,"Pan"->013655,"Path"->000045,"PathComplement"->005843,"Pell"->366504,"PermutationStar"->292991,"Prism"->051927,"Queen"->287227,"Rook"->002720,"RookComplement"->288958,"SierpinskiCarpet"->292707,"SierpinskiGasket"->292708,"SierpinskiTetrahedron"->292697,"Star"->000051,"Sun"->078836,"Sunlet"->080040,"Tetrahedral"->287232,"TorusGrid"->027683,"Transposition"->292709,"Trapezohedron"->366511,"Triangular"->000085,"TriangularGrid"->027740,"TriangularHoneycombAcuteKnight"->287204,"TriangularHoneycombObtuseKnight"->287229,"TriangularHoneycombQueen"->289709,"TriangularHoneycombRook"->000142,"TriangularSnake"->052542,"Web"->287485,"Wheel"->001612,"WheelComplement"->308607,"WhiteBishop"->216078,"Zebra"->366517}]

Parametrized families

<<MathWorld`Graphs`

Alkane

A228602

seq=Table[GraphData[{"Alkane",n},"IndependentVertexSetCount"],{n,10}]

Table[((12-11 Sqrt[2]) (2-2 Sqrt[2])^n+(2 (1+Sqrt[2]))^n (12+11 Sqrt[2]))/8,{n,20}]//Expand

LinearRecurrence[{4,4},{17,80},20]

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

Andrasfai

A288038

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

FindLinearRecurrence[DeleteMissing[seq]]

LinearRecurrence[{5,-8,4},{3,11,33},20]

FindSequenceFunction[DeleteMissing[seq],n]//FullSimplify

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

gf=x FindGeneratingFunction[seq,x]

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

Antiprism

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

A286910

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

FindLinearRecurrence[seq]

seq=LinearRecurrence[{1,2,1},{1,5,10},20]

FindSequenceFunction[seq,n]

FindSequenceFunction[{1,5,10,21,46,98,211,453,973,2090,4489,9642,20710,44483,95545,205221,440794,946781,2033590,4367946},n]

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

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

gf=x FindGeneratingFunction[seq,x]

Apollonian

A289021

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

{1,3}.#&/@NestList[{Total[##^3],#[[1]]#[[2]]^2}&,{1,1},6]

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

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

Looks like it should be related to the IndependencePolynomial, but not directly anyway...

{1,3x}.#&/@NestList[{#[[1]]^3+#[[2]]^3x,#[[1]]#[[2]]^2}&,{x,1},3]//Factor//Column

seq=Table[GraphData[{"Apollonian",n},"IndependencePolynomial"][x],{n,3}]//Column//Factor

Barbell

A005563

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

FindLinearRecurrence[seq]

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

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

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

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

FindSequenceFunction[seq,n-2]//Simplify

Table[n^2-1,{n,42}]

Range[20]^2-1

Bishop n×n

A201862

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

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteMissing[seq],n]

gf=x FindGeneratingFunction[DeleteMissing[seq],x]

Sum[(-1)^m*Binomial[n-i,m]*m^Floor[n/2]*(m+1)^Floor[(n+1)/2],{m,n-i}]

Sum[(-1)^m*Binomial[n-k+i,m]*m^Floor[(n+1)/2]*(m+1)^Floor[n/2],{m,n+i-k}]

knbishops[k_,n_]:=(If[n==1,If[k==1,1,0],(-1)^k/(2n-k)!*Sum[Binomial[2n-k,n-k+i]*Sum[(-1)^m*Binomial[n-i,m]*m^Floor[n/2]*(m+1)^Floor[(n+1)/2],{m,n-i}]*Sum[(-1)^m*Binomial[n-k+i,m]*m^Floor[(n+1)/2]*(m+1)^Floor[n/2],{m,n+i-k}],{i,Max[0,k-n],Min[k,n]}]]);

Table[1+Sum[knbishops[k,n],{k,2n-1}],{n,25}]

BlackBishop n×n

A216332

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

Table[If[Mod[n,2]==0,With[{m=n/2},Sum[Binomial[m,k]BellB[2m-k],{k,0,m}]],With[{m=(n-1)/2},Sum[Binomial[m+1,k]BellB[2m+1-k],{k,0,m+1}]]],{n,20}]

Table[Sum[Binomial[Ceiling[n/2],k]BellB[n-k],{k,0,Ceiling[n/2]}],{n,0,20}]

Sum[Binomial[Ceiling[n/2],k]BellB[n-k],{k,0,Ceiling[n/2]}]

Book

A085279

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

FindLinearRecurrence[seq]

Join[{1},LinearRecurrence[{5,-6},{3,7},20]]

FindSequenceFunction[seq,n]

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

Camel n×n

A366513

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

Centipede

A028859

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

FindSequenceFunction[DeleteMissing[seq],n]//FullSimplify

Table[Sum[Binomial[n-k,k](2^(n-k-1)),{k,0,Floor[n/2]}],{n,10}]

Sum[Binomial[n-k,k](2^(n-k-1)),{k,0,Floor[n/2]}]

(2^(n-1) Hypergeometric2F1[1/2-n/2,-(n/2),-n,-2]/.n->n+1)//Simplify

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

FullSimplify[(2^n) Hypergeometric2F1[-(1/2)-(n/2),-(n/2),-1-n,-2]]

bug(334898): FullSimplify[2^(-1 + n) Hypergeometric2F1[1/2 - n/2, -(n/2), -n, -2]] gives incorrect result

Table[(1/6) (((1+(Sqrt[3])))^n) (3+2 (Sqrt[3])),{n,10}]//Expand

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

gf=x FindGeneratingFunction[seq,x]

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

CocktailParty

A016777

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

3Range[0,20]+1

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

FindLinearRecurrence[seq]

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

seq=Table[3n+1,{n,0,20}]

gf=x FindGeneratingFunction[DeleteMissing[seq],x]

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

Complete

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

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

FindSequenceFunction[seq,n]

CompleteBipartite m×n

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

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

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

CompleteBipartite n×n

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

A000225

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

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

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

FindGeneratingFunction[seq,x]

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

CompleteTripartite k×m×n

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

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

CompleteTripartite n×n×n

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

A033484

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

FindSequenceFunction[seq,n]

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

3 2^Range[0,20]-2

FindLinearRecurrence[seq]

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

gf=x FindGeneratingFunction[seq,x]

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

CrossedPrism

A287327

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

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

Table[((((1/2) (7-(Sqrt[21]))))^n)+((((1/2) (7+(Sqrt[21]))))^n),{n,0,10}]//Expand

FindLinearRecurrence[DeleteMissing@seq]

LinearRecurrence[{7,-7},{7,35},{0,20}]

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

Crown

A083706

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

FindSequenceFunction[seq,n-2]

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

FindLinearRecurrence[DeleteMissing@seq]

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

gf=FindGeneratingFunction[DeleteMissing@seq,x]

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

CubeConnectedCycle

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

A292701

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

Cycle

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

A000032

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

FindSequenceFunction[DeleteCases[seq,_Missing],n-2]//Factor

seq=LucasL[Range[0,20]]

FindGeneratingFunction[seq,x]

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

CycleComplement

A308602

seq=Table[GraphData[{"CycleComplement",n},"IndependentVertexSetCount"],{n,3,20}]

DiagonalIntersection

A291948

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

Dipyramid

A366506

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

FindSequenceFunction[seq,n-2]

(1/2) (6+5 Fibonacci[-2+n]+3 LucasL[-2+n])/.n->n+2

FullSimplify[%]

Table[(6+5 Fibonacci[n]+3 LucasL[n])/2,{n,20}]

FindLinearRecurrence[seq]

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

gf=x FindGeneratingFunction[seq,x]

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

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

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

{(((1-(Sqrt[5])))^2),(((1+(Sqrt[5])))^2)}//Expand//Factor

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

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

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

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

Expand[(2^(-1-n)) (3 (2^(1+n))+2^(n+1) LucasL[n+2])]

Table[LucasL[n]+3,{n,39}]

ToString[%]//StringLength

Table[LucasL[n],{n,39}]

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

LucasL[Range[20]]+3

DorogovtsevGoltsevMendes

A368456

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

b[0]=c[0]=1;
a[n_]:=a[n]=b[n]+2c[n]
b[n_]:=b[n]=c[n]+b[n-1]^3 
c[n_]:=c[n]=b[n-1]c[n-1]^2

Array[a,7]

Clear[a,b,c]

RSolve[{b[0]==c[0]==1,a[n]==b[n]+2c[n],b[n]==c[n]+b[n-1]^3 ,c[n]==b[n-1]c[n-1]^2},{a[n],b[n],c[n]},n]

RecurrenceTable[{b[0]==c[0]==1,a[n]==b[n]+2c[n],b[n]==c[n]+b[n-1]^3 ,c[n]==b[n-1]c[n-1]^2},a,{n,1,10}]

DoubleCone

A366508

seq=Table[GraphData[{"DoubleCone",n},"IndependentVertexSetCount"],{n,3,20}]

FindSequenceFunction[seq,n-2]//FullSimplify

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

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

FindLinearRecurrence[seq]

seq=LinearRecurrence[{3,0,-3,1},{2,10,17,50},20]

gf=x FindGeneratingFunction[seq,x]

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

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

Empty

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

A000079

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

FindSequenceFunction[seq,n]

seq=2^Range[0,20]

FindLinearRecurrence[seq]

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

FindGeneratingFunction[seq,x]

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

FibonacciCube

A291936

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

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

Fiveleaper n×n

A293150

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

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

Flower

A366516

seq=Table[GraphData[{"Flower",n},"IndependentVertexSetCount"],{n,5,20}]

FoldedCube

A290888

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

Gear

A287350

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

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

seq=Table[2^n+LucasL[2 n],{n,20}]

FindLinearRecurrence[DeleteMissing@seq]

LinearRecurrence[{5,-7,2}

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

GeneralizedPetersen

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

Giraffe n×n

A366514

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

Goldberg

A366515

seq=Table[GraphData[{"Goldberg",n},"IndependentVertexSetCount"],{n,3,20}]

Grid 3×n

A051736

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

coef=FindLinearRecurrence[DeleteMissing@seq]

Take[seq,Length[coef]]

seq=LinearRecurrence[{2,6,0,-1},{5,17,63,227},{0,20}]

FindSequenceFunction[DeleteMissing@seq,n]

gf=FindGeneratingFunction[DeleteMissing@seq,x]

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

res=Refine[SeriesCoefficient[gf,{x,0,n}],n>0]

FullSimplify[RootReduce[res],n>0]

f1=1-6 ((#1)^2)-2 ((#1)^3)+((#1)^4)&;
f2=1-38 #1-776 ((#1)^2)-1994 ((#1)^3)+1994 ((#1)^4)&;

pos={2,1,3,4};

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

Equal@@Last/@an

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

Table[-((RootSum[1-6 ((#1)^2)-2 ((#1)^3)+((#1)^4)&,263 ((#1)^n)-657 ((#1)^(n+1))-331 ((#1)^(n+2))+81 ((#1)^(n+3))&])/1994),{n,0,20}]

Grid m×n

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

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

Grid n×n

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

A006506

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Table[With[{g=System`GridGraph[{n,n}]},Count[Subsets[Range[n^2],Length@First@FindIndependentVertexSet[g]],_?(IndependentVertexSetQ[g,#]&)]],{n,5}]

Grid k×m×n

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

Grid n×n×n

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

A292702

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

HalvedCube

A288943

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

Hanoi

A288490

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

Next(h0, h1, h2, h3) = {[h0^3 + 6*h0^2*h1 + 9*h0*h1^2 + 3*h0^2*h2 + 2*h1^3 + 6*h0*h1*h2, h0^2*h1 + 4*h0*h1^2 + 2*h0^2*h2 + h0^2*h3 + 8*h0*h1*h2 + 3*h1^3 + 4*h1^2*h2 + 2*h0*h2^2 + 2*h0*h1*h3, h0*h1^2 + 4*h0*h1*h2 + 2*h1^3 + 7*h1^2*h2 + 2*h0*h1*h3 + 3*h0*h2^2 + 4*h1*h2^2 + 2*h1^2*h3 + 2*h0*h2*h3, h1^3 + 6*h1^2*h2 + 9*h1*h2^2 + 3*h1^2*h3 + 2*h2^3 + 6*h1*h2*h3]}
a(n) = {my(v); v=[1, 1, 0, 0]; for(i=2, n, v=Next(v[1], v[2], v[3], v[4])); v[1]+v[4]+3*(v[2]+v[3])}

{1,3,3,1}.#&/@NestList[{#[[1]]^3+6#[[1]]^2#[[2]]+9#[[1]]#[[2]]^2+3#[[1]]^2#[[3]]+2#[[2]]^3+6#[[1]]#[[2]]#[[3]],#[[1]]^2#[[2]]+4#[[1]]#[[2]]^2+2#[[1]]^2#[[3]]+#[[1]]^2#[[4]]+8#[[1]]#[[2]]#[[3]]+3#[[2]]^3+4#[[2]]^2#[[3]]+2#[[1]]#[[3]]^2+2#[[1]]#[[2]]#[[4]],#[[1]]#[[2]]^2+4#[[1]]#[[2]]#[[3]]+2#[[2]]^3+7#[[2]]^2#[[3]]+2#[[1]]#[[2]]#[[4]]+3#[[1]]#[[3]]^2+4#[[2]]#[[3]]^2+2#[[2]]^2#[[4]]+2#[[1]]#[[3]]#[[4]],#[[2]]^3+6#[[2]]^2#[[3]]+9#[[2]]#[[3]]^2+3#[[2]]^2#[[4]]+2#[[3]]^3+6#[[2]]#[[3]]#[[4]]}&,{1,1,0,0},4]

IntegerLength[{1,3,3,1}.#]&/@NestList[{#[[1]]^3+6#[[1]]^2#[[2]]+9#[[1]]#[[2]]^2+3#[[1]]^2#[[3]]+2#[[2]]^3+6#[[1]]#[[2]]#[[3]],#[[1]]^2#[[2]]+4#[[1]]#[[2]]^2+2#[[1]]^2#[[3]]+#[[1]]^2#[[4]]+8#[[1]]#[[2]]#[[3]]+3#[[2]]^3+4#[[2]]^2#[[3]]+2#[[1]]#[[3]]^2+2#[[1]]#[[2]]#[[4]],#[[1]]#[[2]]^2+4#[[1]]#[[2]]#[[3]]+2#[[2]]^3+7#[[2]]^2#[[3]]+2#[[1]]#[[2]]#[[4]]+3#[[1]]#[[3]]^2+4#[[2]]#[[3]]^2+2#[[2]]^2#[[4]]+2#[[1]]#[[3]]#[[4]],#[[2]]^3+6#[[2]]^2#[[3]]+9#[[2]]#[[3]]^2+3#[[2]]^2#[[4]]+2#[[3]]^3+6#[[2]]#[[3]]#[[4]]}&,{1,1,0,0},7]

Helm

A287594

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

FindSequenceFunction[seq,n-2]//FullSimplify

Table[2^n+2^(n/2) LucasL[n,Sqrt[2]],{n,0,20}]//Round

FindLinearRecurrence[seq]

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

gf=x FindGeneratingFunction[seq,x]

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

Hypercube

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

A027624

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

Do[Print[{n,Length[FindAllIndependentVertexSets[GraphData[{"Hypercube",n}]]]//Timing,MaxMemoryUsed[]/10^9.GB}],{n,7}]

Table[Length[Union@@(Subsets/@FindIndependentVertexSet[HypercubeGraph[n],Infinity,All])],{n,0,5}]

Keller

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

A284854

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

King m×n

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

King 2×n

A001045

Jacobsthal numbers

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

FindLinearRecurrence[seq]

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

FindSequenceFunction[seq,n]//FullSimplify

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

gf=x FindGeneratingFunction[seq,x]

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

King n×n

A063443

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

Algorithm 1

(* Mark McClure (mcmcclur(AT)bulldog.unca.edu) Mar 19 2006 *)

step[sa[rules1_,{dim1_,dim1_}],sa[rules2_,{dim2_,dim2_}]]:=sa[Join[rules2,rules1/.{x_Integer,y_Integer}->{x+dim2,y},rules1/.{x_Integer,y_Integer}->{x,y+dim2}],{dim1+dim2,dim1+dim2}];
mat[0]=sa[{{1,1}->1},{1,1}];mat[1]=sa[{{1,1}->1,{1,2}->1,{2,1}->1},{2,2}];mat[n_]:=mat[n]=step[mat[n-2],mat[n-1]];A[n_]:=mat[n]/.sa->SparseArray;Table[MatrixPower[A[n],n+1][[1,1]],{n,010}]

Algorithm 2

(* Jean-François Alcover, Dec 11 2014, after Alois P.Heinz *)

Clear[a,b];b[n_,l_List]:=b[n,l]=Module[{m=Min[l],k},If[m>0,b[n-m,l-m],If[n==0,1,k=Position[l,0,1,1][[1,1]];b[n,ReplacePart[l,k->1]]+If[n>1&&k<Length[l]&&l[[k+1]]==0,b[n,ReplacePart[l,{k->2,k+1->2}]],0]]]];a[n_]:=a[n]=If[n<2,1,b[n,Table[0,{n}]]];

Array[a,15]

Knight m×n

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

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

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

Knight n×n

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

A141243

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

b[n_,l_]:=b[n,l]=Module[{d,f,g,k},d=Length[l]/3;f=False;Which[n==0,1,l[[1;;d]]==Array[f&,d],b[n-1,Join[l[[d+1;;3*d]],Array[True&,d]]],True,For[k=1,!l[[k]],k++];g=ReplacePart[l,k->f];
If[k>1,g=ReplacePart[g,2*d-1+k->f]];
If[k<d,g=ReplacePart[g,2*d+1+k->f]];
If[k>2,g=ReplacePart[g,d-2+k->f]];
If[k<d-1,g=ReplacePart[g,d+2+k->f]];
Expand[b[n,ReplacePart[l,k->f]]+b[n,g]*x]]];
a[n_]:=Function[p,Sum[Coefficient[p,x,i],{i,0,Exponent[p,x]}]][b[n,Array[True&,3n]]];

Array[a,8]

Ladder

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

A001333

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]//FullSimplify

Table[(-I)^n ChebyshevT[n,I],{n,10}]

FindLinearRecurrence[DeleteCases[seq,_Missing]]

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

seq=Join[{1},Numerator[Convergents[Sqrt[2],20]]]

gf=x FindGeneratingFunction[DeleteCases[seq,_Missing],x]

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

LadderRung

A000244

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

FindSequenceFunction[seq,n]

FindLinearRecurrence[seq]

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

FindGeneratingFunction[seq,x]

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

LucasCube

A366505

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

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

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

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

MengerSponge

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

MiddleLayer

A366518

seq=Table[GraphData[{"MiddleLayer",n},"IndependentVertexSetCount"],{n,5}]

MoebiusLadder

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

A182143

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

FullSimplify[FindSequenceFunction[seq,n-2]]

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

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

FindLinearRecurrence[DeleteMissing[seq]]

seq=LinearRecurrence[{1,3,1},{1,3,5},20]

FindGeneratingFunction[seq,x]

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

Mycielski

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

A292710

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

FindSequenceFunction[DeleteMissing@seq,n]

Odd

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

A292711

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

FindSequenceFunction[DeleteMissing@seq,n]

Pan

A001060

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

FindSequenceFunction[seq,n-2]//FullSimplify

Table[Fibonacci[n+2]+LucasL[n+1],{n,0,40}]

FindLinearRecurrence[DeleteMissing@seq]

seq=LinearRecurrence[{1,1},{2,5},50]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

Path

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

A000045

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

Fibonacci[Range[20]+2]

FindGeneratingFunction[Fibonacci[Range[0,20]],x]

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

Pell

A366504

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

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

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

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

PermutationStar

A292991

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

Prism

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

A051927

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

FullSimplify[FindSequenceFunction[seq,n-2],n>0]

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

FindLinearRecurrence[DeleteMissing[seq]]

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

gf=FindGeneratingFunction[DeleteMissing[seq],x]

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

Queen n×n

A287227

seq=Table[GraphData[{"Queen",{n,n}},"IndependentVertexSetCount"],{n,20}]

Length@DeleteMissing@seq

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

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

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

Rook n×n

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

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

Sum[k!((Binomial[n,k])^2),{k,0,n}]

FunctionExpand[%]

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

FindLinearRecurrence[DeleteMissing[seq]]

FindSequenceFunction[DeleteCases[seq,_Missing],n]

gf=x FindGeneratingFunction[DeleteCases[seq,_Missing],x]

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

RookComplement n×n

A288958

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

FindSequenceFunction[Rest@seq,n-1]

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

SierpinskiCarpet

A292707

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

SierpinskiSieve

A292708

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

SierpinskiTetrahedron

A292697

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

Star

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

A000051

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

FindSequenceFunction[seq,n]//FullSimplify

FindLinearRecurrence[seq]

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

Sun

A078836

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

FindLinearRecurrence[DeleteCases[seq,_Missing]]

LinearRecurrence[{4,-4},{6,14},20]

seq=Table[i*2^(i-6),{i,6,20}]

FindSequenceFunction[DeleteCases[seq,_Missing],n-2]//FullSimplify

gf=FindGeneratingFunction[seq,x]

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

Sunlet

A080040

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

Round@Table[LucasL[n,Sqrt[2]]2^(n/2),{n,20}]

FindLinearRecurrence[DeleteCases[seq,_Missing]]

LinearRecurrence[{2,2},{2,8},20]

FindSequenceFunction[DeleteCases[seq,_Missing],n-2]//FullSimplify

Table[(((1-(Sqrt[3])))^n)+(((1+(Sqrt[3])))^n),{n,0,20}]//Expand

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

Tetrahedral

A287232

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

Do[Print[{{"Tetrahedral",n},IndependencePolynomial[TetrahedralGraph[n],x]//Timing}],{n,6,10}]

seq=%[[All,2,2]]/.x->1

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

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

From duplicate/overlapping A323293:

stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];

Do[Print[{n,Length[stableSets[Subsets[Range[n],{3}],Length[Intersection[#1,#2]]>1&]]//Timing}],{n,10}]

TorusGrid n×n

A027683

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

seq=BFileSequence[027683]

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

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

a[n_]:=With[{sets=Select[Tuples[{0,1},n],Count[# RotateLeft[#],1]==0&]},Tr[MatrixPower[Table[Boole[Count[s1 s2,1]==0],{s1,sets},{s2,sets}],n]]];

Do[Print[{{"TorusGrid",{n,n}},a[n]//Timing}],{n,3,20}]

Transposition

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

A292709

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

Trapezohedron

A366511

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

FindSequenceFunction[seq,n-2]//FullSimplify

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

Table[LucasL[2n],{n,10}]

seq=Table[LucasL[2n]+(2^(n+1))+1,{n,29}]

FindLinearRecurrence[seq]

seq=LinearRecurrence[{6,-12,9,-2},{8,16,35,80},20]

gf=x FindGeneratingFunction[seq,x]

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

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

Triangular

A000085

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

FindLinearRecurrence[DeleteCases[seq,_Missing]]

FindSequenceFunction[DeleteCases[seq,_Missing],n-1]

Table[(I/Sqrt[2])^n HermiteH[n,-I/Sqrt[2]],{n,20}]

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

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

TriangularGrid

A027740

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

Length@DeleteMissing@seq

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

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

TriangularHoneycombAcuteKnight

A287204

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

seq={2,8,27,144,1331,13824,208575,4741632,140608000,5870657088,350253538649,28635764824584,3270761581689147,524882236329014264,117025388905265182783,36405238728128712859232,15833111238624255435917875,9599917578598545475054063616};

FindLinearRecurrence[seq]

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

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

TriangularHoneycombBishop

A000110

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

BellB[1+Range[20]]==seq

Series[Hypergeometric1F1[-1/x,(x-1)/x,1]/E,{x,0,10}]

Sum[(1/((1-k x)k!)),{k,0,∞}]/E//FullSimplify

Plot[(((((-1))^(1/x)) Gamma[-(1/x),0,-1])/(E x)),{x,-.2,1/4},WorkingPrecision->20,PlotPoints->100]

Series[-(((((-1))^(1/x)) Gamma[-(1/x),0,-1])/(E x)),{x,0,10}]

GeneratingFunction[BellB[n],n,x]

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

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

TriangularHoneycombObtuseKnight

A287229

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

Length@DeleteMissing@seq

Head/@Table[FindLinearRecurrence[Drop[DeleteMissing@seq,k]],{k,0,2}]

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

TriangularHoneycombQueen

A289709

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

Length@DeleteMissing@seq

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

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

TriangularHoneycombRook

A000142

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

FindSequenceFunction[seq,n]//FunctionExpand//FullSimplify

Table[(n+1)!,{n,10}]

Web

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

Table[RootSum[-4-8 #-2 #^2+#^3&,#^n&],{n,20}]

FindLinearRecurrence[DeleteCases[seq,_Missing]]

seq=LinearRecurrence[{2,8,4},{2,20,68},20]

gf=x FindGeneratingFunction[DeleteCases[seq,_Missing],x]

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

Wheel

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

A001612

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

FindLinearRecurrence[seq]

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

FindSequenceFunction[seq,n-3]//FullSimplify

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

FindSequenceFunction[{3,2,4,5,8,12,19,30,48,77,124,200,323,522,844,1365,2208,3572,5779,9350},n]

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

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

FindGeneratingFunction[seq,x]

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

WhiteBishop n×n

A216078

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

seq={3,7,27,87,409,1657,9089,43833,272947,1515903,10515147,65766991,501178937,3473600465,28773452321,218310229201,1949230218691,16035686850327,153281759047387,1356791248984295,13806215066685433};

FindLinearRecurrence[seq]

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

a[n_]:=Module[{m,e},{m,e}=QuotientRemainder[n-1,2];Sum[Binomial[m,k]*BellB[m+k+e],{k,0,m}]]

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

Zebra n×n

A366517

seq=Table[GraphData[{"Zebra",{n,n}},"IndependentVertexSetCount"],{n,10}]